题意：给定简单无向图，求一个最小的边集使得这些点是边双，输出方案。n <= 14
解：考虑一个边双肯定是一条一条的链拼起来的。于是每次枚举一条链加上去就行了。
设fs表示点集s形成边双的最小边数。linki,j,s表示点集s能否形成一个i - j的链。link2x,s表示点x和点集s是否直接相连。
上面这些数组都要记录方案，特别地，link2要记录两个方案，为了应对拼上去的链退化成一个点的情况。
#include <bits/stdc++.h>
const int N = ;
struct Edge {
int nex, v;
}edge[N << ]; int tp;
struct Node {
int x, y, t;
Node(int X = , int Y = , int T = ) {
x = X;
y = Y;
t = T;
}
}fr3[N];
int pw[N], cnt[N], f[N], e[N], n, m;
bool link[][][N], link2[][N];
int fr[][][N], fr2[][N], fr22[][N];
inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void out(int x, int y, int s) {
if(cnt[s] == ) return;
printf("%d %d \n", y + , fr[x][y][s]);
out(x, fr[x][y][s] - , s ^ ( << y));
return;
}
void out3(int s) {
if(cnt[s] == ) return;
int x = fr3[s].x, y = fr3[s].y, t = fr3[s].t;
out(x, y, t);
printf("%d %d \n", x + , fr2[x][s ^ t]);
if(x != y) printf("%d %d \n", y + , fr2[y][s ^ t]);
else printf("%d %d \n", y + , fr22[y][s ^ t]);
out3(s ^ t);
return;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = , x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
int lm = ( << n) - ; /// lm = 111111...1
for(int i = ; i <= lm; i++) {
cnt[i] = + cnt[i - (i & (-i))];
if(i > ) pw[i] = pw[i >> ] + ;
}
for(int x = ; x < n; x++) {
for(int s = ; s <= lm; s++) {
/// link2[x][s]
if((s >> x) & ) continue;
for(int i = e[x + ]; i; i = edge[i].nex) {
int y = edge[i].v - ;
if((s >> y) & ) {
link2[x][s] = ;
if(!fr2[x][s]) {
fr2[x][s] = y + ;
}
else {
fr22[x][s] = y + ;
break;
}
}
}
}
}
for(int i = ; i < n; i++) {
link[i][i][ << i] = ;
}
for(int s = ; s < lm; s++) {
for(int t1 = s, i; t1; t1 ^= ( << i)) {
i = pw[t1 & (-t1)];
/// i + 1
for(int t2 = s, x; t2; t2 ^= ( << x)) {
x = pw[t2 & (-t2)];
/// f[i][x][s]
if(!link[i][x][s]) continue;
for(int j = e[x + ]; j; j = edge[j].nex) {
int y = edge[j].v - ;
if(((s >> y) & ) == ) {
link[i][y][s | ( << y)] = ;
fr[i][y][s | ( << y)] = x + ;
}
}
}
}
}
memset(f, 0x3f, sizeof(f));
f[] = ;
for(int s = ; s <= lm; s++) {
/// f[s]
for(int t = s & (s - ); t; t = (t - ) & s) {
for(int t1 = t, x; t1; t1 ^= ( << x)) {
x = pw[t1 & (-t1)];
for(int t2 = t, y; t2; t2 ^= ( << y)) {
y = pw[t2 & (-t2)];
/// link[x][y][t] link2[x][s ^ t] link2[y][s ^ t]
if(link[x][y][t] && link2[x][s ^ t] && link2[y][s ^ t] && (x != y || fr22[x][s ^ t])) {
if(f[s] > f[s ^ t] + cnt[t] + ) {
f[s] = f[s ^ t] + cnt[t] + ;
fr3[s] = Node(x, y, t);
}
}
}
}
}
}
printf("%d\n", f[lm]);
out3(lm);
return ;
}
AC代码