题意就是选一些权值和最小的边,使得图 边双连通。\(n\) 很小,应该是个状压 \(DP\) , 如何转移呢?

注意到任何一个边双都可以通过一个子边双加一条链得到。就按这个 \(DP\) ,预处理 \(g(s,i,j)\) 表示 \(s\) 中的点构成头尾为 \(i\) , \(j\) 的一条链的最小代价,设 \(f(s)\) 表示 \(s\) 构成一个边双的最小代价,每次加链转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=20, maxe=90;
int n,m,INF;
int fir[maxn],son[maxe],nxt[maxe],w[maxe],tot;
void add(int x,int y,int z){
son[++tot]=y; w[tot]=z; nxt[tot]=fir[x]; fir[x]=tot;
}
int g[(1<<12)+5][20][20],h[(1<<12)+5][20][2];
inline void Min_eq(int &x,int y){
x=min(x,y);
}
inline void Pre(){
memset(h,63,sizeof(h)); INF=h[0][0][0];
for(int s=1;s<=(1<<n)-1;s++){
for(int i=1;i<=n;i++){
int t0=INF, t1=INF;
for(int j=fir[i];j;j=nxt[j])
if((s>>son[j]-1)&1){
if(w[j]<t0) t1=t0, t0=w[j];
else if(w[j]<t1) t1=w[j];
}
h[s][i][0]=t0; h[s][i][1]=t1;
}
}
memset(g,63,sizeof(g));
for(int i=1;i<=n;i++) g[1<<i-1][i][i]=0;
for(int s=1;s<=(1<<n)-1;s++)
for(int i=1;i<=n;i++)
if((s>>i-1)&1)
for(int j=1;j<=n;j++)
if(((s>>j-1)&1)&&g[s][i][j]<INF){
int _g=g[s][i][j];
for(int k=fir[i];k;k=nxt[k]) if(!((s>>son[k]-1)&1)) Min_eq(g[s|(1<<son[k]-1)][son[k]][j],_g+w[k]);
for(int k=fir[j];k;k=nxt[k]) if(!((s>>son[k]-1)&1)) Min_eq(g[s|(1<<son[k]-1)][i][son[k]],_g+w[k]);
}
}
int _test,f[(1<<12)+5];
int main(){
freopen("bzoj3590.in","r",stdin);
freopen("bzoj3590.out","w",stdout);
_test=getint();
while(_test--){
n=getint(); m=getint();
memset(fir,0,sizeof(fir)); tot=0;
for(int i=1;i<=m;i++){
int x=getint(),y=getint(),z=getint();
add(x,y,z); add(y,x,z);
}
Pre();
memset(f,63,sizeof(f));
for(int i=1;i<=n;i++) f[1<<i-1]=0;
for(int s=1;s<=(1<<n)-2;s++){
int _s=((1<<n)-1)^s;
for(int i=1;i<=n;i++) if(!((s>>i-1)&1)&&h[s][i][1]<INF) Min_eq(f[s|(1<<i-1)],f[s]+h[s][i][0]+h[s][i][1]);
for(int t=_s;t>0;t=(t-1)&_s){
for(int i=1;i<=n;i++)
if((t>>i-1)&1)
for(int j=1;j<=n;j++)
if(i!=j&&((t>>j-1)&1)&&g[t][i][j]<INF&&h[s][i][0]<INF&&h[s][j][0]<INF)
f[s|t]=min(f[s|t],f[s]+g[t][i][j]+h[s][i][0]+h[s][j][0]);
}
}
f[(1<<n)-1]<INF?printf("%d\n",f[(1<<n)-1]):puts("impossible");
}
return 0;
}