本文共 2030 字，大约阅读时间需要 6 分钟。

题意

给你一个无向图，并告诉你有k条边是一定要走的，有m条边是可走可不走。然后问你从1号点出发，经过所有的k条边，最后回到1号点的最小代价

前言

这题我做了很久，好像差不多有一个下午加晚上吧。。

一开始找到Claris的题解。。不是很敢弄。。 然后发现dis里面似乎有新大陆，于是又弄了很久。。但是一直没有弄出什么东西来 最后还是回去了Claris的做法 然后弄懂了之后，还是不是很敢再打一次，因为上一次大部分都是参考Claris的。 我就来认真地口胡一篇博客来假装自己会了吧。。

题解

我们分成两种情况讨论，K$≤$15,和k

>

$>$15

为什么要分这两种情况

因为我们可以发现，当k$>$15的时候，由于n的最大值只有13，所以他至多只会有7个联通块，达到最大联通块的方案是，6个点里面互相连边，然后这里是15条边，此时有 剩下的7个点+1个联通块=8个联通块，然后无论你下一个加到哪里，比减少一个联通块，于是就是7个了。。

我们考虑最后的答案，如果所有包含关键边的联通块都和1号点属于联通块的话，那么至少说明，这个方案有可能可行的 但是还是有一种不存在回路的情况。。 根据无向图是否存在欧拉回路的判定方法，如果所有点的度数都是偶数，那么就存在一条欧拉回路。。 于是我们可以断定，如果在最后的状态里面，如果该状态的关键边与1号点连通且度数均为偶数，那么就是可行的

K$≤$15

这个很好办，考虑到k很小，我们不妨状压一下每一条关键边的经过状态，然后搭上当前在哪个点，就可以出来一个最短路了，f[i][j]表示当前在i号点，经过状态为j的最小代价

时间复杂度$O(n*2^{15})$然后用dij跑的话应该还是多一个log的

代码实现:

int f[N][N][2],g[N][N],d[N][(1<
    
     ,greater
     
       >q;    void ext (int x,int y,int z)//看看之前是否存在这个状态    //x现在在哪一个点   走的那些边状态是什么     {        if (d[x][y]<=z) return ;        q.push(PI(d[x][y]=z,P(x,y)));    }    void solve ()    {        for (int u=0;u
      
       d[x][y]) continue;            for (int u=0;u
      
     
    

K>15

这种情况就不是特别好办了。。

但是读了第一部分的人都知道，此时我们用尽各种奇技淫巧，可以吧一个图缩成7个联通块。而7个联通块的连接状态，其实就是，这个如果有研究过数论的就都知道。感觉在看斯特林数的时候经常可以看到这个（暴露智商）。$Bell(7)$是只有877个状态的，于是我们就可以位压了。。 不妨DPf[i][j][k]表示用了前i条边，然后连通状态为j，每个点的奇偶状态为k的最小代价是什么。。 然后DP一下就就可以了 同时为了处理方便，我们可以引入一个g数组，和q数组 q预先吧所有状态都处理出来，放在里面， 也就是上面的j不是一个状态，只是状态的一个编号而已 然后g表示某一个状态加上某一条边会到达什么状态，这就可以实现了 代码实现：

int a[N];//前期：作为并查集   后期：辅助数组    int dp[2][1<
   
    id;    int o=0,h=0,t=0;    LL q[M];    void Merge (int x,int y)//这两个点连在一起     {        x=a[x];y=a[y];        for (int u=0;u
    
     =0;u--)            a[u]=(f&15),f>>=4;    }    int ext (LL x)    {        //看看是否存在x这个状态，并给他标号         if (id[x]!=0) return id[x];        id[x]=++t;        q[id[x]]=x;        return id[x];    }    void clr ()    {        T++;        for (int u=1;u<=t;u++) cnt[o^1][u]=0;    }    void add (int x,int y,int z)    {        if (z>=MAX) return ;        if (v[o^1][x][y]
     
      y) swap(x,y);            up(e[x][y],z);        }        clr();        for (int u=0;u<(1<