题意：给定简单无向图，求一个最小的边集使得这些点是边双，输出方案。n <= 14
解：考虑一个边双肯定是一条一条的链拼起来的。于是每次枚举一条链加上去就行了。
设fs表示点集s形成边双的最小边数。linki,j,s表示点集s能否形成一个i - j的链。link2x,s表示点x和点集s是否直接相连。
上面这些数组都要记录方案，特别地，link2要记录两个方案，为了应对拼上去的链退化成一个点的情况。
1 #include <bits/stdc++.h> 2 3 const int N = 20000; 4 5 struct Edge { 6 int nex, v; 7 }edge[N << 1]; int tp; 8 9 struct Node { 10 int x, y, t; 11 Node(int X = 0, int Y = 0, int T = 0) { 12 x = X; 13 y = Y; 14 t = T; 15 } 16 }fr3[N]; 17 18 int pw[N], cnt[N], f[N], e[N], n, m; 19 bool link[20][20][N], link2[20][N]; 20 int fr[20][20][N], fr2[20][N], fr22[20][N]; 21 22 inline void add(int x, int y) { 23 tp++; 24 edge[tp].v = y; 25 edge[tp].nex = e[x]; 26 e[x] = tp; 27 return; 28 } 29 30 void out(int x, int y, int s) { 31 if(cnt[s] == 1) return; 32 printf("%d %d ", y + 1, fr[x][y][s]); 33 out(x, fr[x][y][s] - 1, s ^ (1 << y)); 34 return; 35 } 36 37 void out3(int s) { 38 if(cnt[s] == 1) return; 39 int x = fr3[s].x, y = fr3[s].y, t = fr3[s].t; 40 out(x, y, t); 41 printf("%d %d ", x + 1, fr2[x][s ^ t]); 42 if(x != y) printf("%d %d ", y + 1, fr2[y][s ^ t]); 43 else printf("%d %d ", y + 1, fr22[y][s ^ t]); 44 out3(s ^ t); 45 return; 46 } 47 48 int main() { 49 scanf("%d%d", &n, &m); 50 for(int i = 1, x, y; i <= m; i++) { 51 scanf("%d%d", &x, &y); 52 add(x, y); 53 add(y, x); 54 } 55 int lm = (1 << n) - 1; /// lm = 111111...1 56 for(int i = 1; i <= lm; i++) { 57 cnt[i] = 1 + cnt[i - (i & (-i))]; 58 if(i > 1) pw[i] = pw[i >> 1] + 1; 59 } 60 61 for(int x = 0; x < n; x++) { 62 for(int s = 1; s <= lm; s++) { 63 /// link2[x][s] 64 if((s >> x) & 1) continue; 65 for(int i = e[x + 1]; i; i = edge[i].nex) { 66 int y = edge[i].v - 1; 67 if((s >> y) & 1) { 68 link2[x][s] = 1; 69 if(!fr2[x][s]) { 70 fr2[x][s] = y + 1; 71 } 72 else { 73 fr22[x][s] = y + 1; 74 break; 75 } 76 } 77 } 78 } 79 } 80 81 for(int i = 0; i < n; i++) { 82 link[i][i][1 << i] = 1; 83 } 84 for(int s = 1; s < lm; s++) { 85 for(int t1 = s, i; t1; t1 ^= (1 << i)) { 86 i = pw[t1 & (-t1)]; 87 /// i + 1 88 for(int t2 = s, x; t2; t2 ^= (1 << x)) { 89 x = pw[t2 & (-t2)]; 90 /// f[i][x][s] 91 if(!link[i][x][s]) continue; 92 for(int j = e[x + 1]; j; j = edge[j].nex) { 93 int y = edge[j].v - 1; 94 if(((s >> y) & 1) == 0) { 95 link[i][y][s | (1 << y)] = 1; 96 fr[i][y][s | (1 << y)] = x + 1; 97 } 98 } 99 } 100 } 101 } 102 103 memset(f, 0x3f, sizeof(f)); 104 f[1] = 0; 105 for(int s = 2; s <= lm; s++) { 106 /// f[s] 107 for(int t = s & (s - 1); t; t = (t - 1) & s) { 108 for(int t1 = t, x; t1; t1 ^= (1 << x)) { 109 x = pw[t1 & (-t1)]; 110 for(int t2 = t, y; t2; t2 ^= (1 << y)) { 111 y = pw[t2 & (-t2)]; 112 /// link[x][y][t] link2[x][s ^ t] link2[y][s ^ t] 113 if(link[x][y][t] && link2[x][s ^ t] && link2[y][s ^ t] && (x != y || fr22[x][s ^ t])) { 114 if(f[s] > f[s ^ t] + cnt[t] + 1) { 115 f[s] = f[s ^ t] + cnt[t] + 1; 116 fr3[s] = Node(x, y, t); 117 } 118 } 119 } 120 } 121 } 122 } 123 124 printf("%d ", f[lm]); 125 out3(lm); 126 return 0; 127 }