算法原理详见 http://www.csie.ntnu.edu.tw/~u91029/Matching.html
orz 带花树很神奇，挖坑最大权匹配
#include#include #include #include using namespace std;const int maxn = 50;deque p[maxn]; //树根到x的交错路径bool adj[maxn][maxn];int m[maxn]; //记录匹配情况int d[maxn]; //记录奇点和偶点int q[maxn], *qf, *qb; //记录可延伸的偶点int n;void label_one_side(int x, int y, int bi){ for(int i = bi+1; i < p[x].size(); i++){ int z = p[x][i]; if(d[z] == 1){ p[z] = p[y]; p[z].insert(p[z].end(), p[x].rbegin(), p[x].rend()-i); d[z] = 0; *qb++ = z; } }}bool BFS(int r){ for(int i = 0; i < n; i++) p[i].clear(); p[r].push_back(r); for(int i = 0; i < n; i++) d[i] = -1; d[r] = 0; qf = qb = q; *qb++ = r; while(qf < qb){ for(int x = *qf++, y = 0; y < n; y++){ if(adj[x][y] && m[y] != y){ if(d[y] == -1){ if(m[y] == -1){ for(int i = 0; i+1 < p[x].size(); i += 2){ m[p[x][i]] = p[x][i+1]; m[p[x][i+1]] = p[x][i]; } m[x] = y; m[y] = x; return true; } else { int z = m[y]; p[z] = p[x]; p[z].push_back(y); p[z].push_back(z); d[y] = 1; d[z] = 0; *qb++ = z; } } else if(d[y] == 0) { int bi = 0; while(bi < p[x].size() && bi < p[y].size() && p[x][bi] == p[y][bi]) bi++; bi--; label_one_side(x, y, bi); label_one_side(y, x, bi); } } } } return false;}int match(){ for(int i = 0; i < n; i++) m[i] = -1; int c = 0; for(int i = 0; i < n; i++){ if(m[i] == -1) if(BFS(i)) c++; else m[i] = i; } return c;}int main(){ cin>>n; int x, y; while(cin>>x>>y) adj[x][y] = adj[y][x] = true; match();}
这个是缩点版本的
#include#include #include using namespace std;const int N = 50;int n;bool adj[N][N];int p[N];int m[N];int d[N];int c1[N], c2[N];int q[N], *qf, *qb;int pp[N];int f(int x) { return x == pp[x] ? x : pp[x] = f(pp[x]); }void u(int x, int y) { pp[x] = y; }int v[N];void path(int r, int x){ if(r == x) return; if(d[x] == 0){ path(r, p[p[x]]); int i = p[x], j = p[p[x]]; m[i] = j; m[j] = i; } else if(d[x] == 1){ path(m[x], c1[x]); path(r, c2[x]); int i = c1[x], j = c2[x]; m[i] = j; m[j] = i; }}int lca(int x, int y, int r){ int i = f(x), j = f(y); while(i != j && v[i] != 2 && v[j] != 1){ v[i] = 1; v[j] = 2; if(i != r) i = f(p[i]); if(j != r) j = f(p[j]); } int b = i, z = j; if(v[j] == 1) swap(b, z); for(int i = b; i != z; i = f(p[i])) v[i] = -1; v[z] = -1; return b;}void contract_one_side(int x, int y, int b){ for(int i = f(x); i != b; i = f(p[i])){ u(i, b); if(d[i] == 1) c1[i] = x, c2[i] = y, *qb++ = i; }}bool BFS(int r){ for(int i = 0; i < n; i++) pp[i] = i; for(int i = 0; i < n; i++) v[i] = d[i] = -1; d[r] = 0; qf = qb = q; *qb++ = r; while(qf < qb){ for(int x = *qf++, y = 0; y < n; y++){ if(!adj[x][y] || m[y] == y || f(x) == f(y)) continue; if(d[y] == -1){ if(m[y] == -1){ path(r, x); m[x] = y; m[y] = x; return true; } else { p[y] = x; p[m[y]] = y; d[y] = 1; d[m[y]] = 0; *qb++ = m[y]; } } else if(d[f(y)] == 0){ int b = lca(x, y, r); contract_one_side(x, y, b); contract_one_side(y, x, b); } } } return false;}int main(){}