简述一下“带花树”算法吧：
它的核心思想还是找增广路。假设已经匹配好了一堆点，我们从一个没有匹配的节点s开始，使用BFS生成搜索树。每当发现一个节点u，如果u还没有被匹配，那么就可以进行一次成功的增广；否则，我们就把节点u和它的配偶v一同接到树上，之后把ｖ丢进队列继续搜索。我们给每个在搜索树上的点一个类型：S或者T。当ｕ把它的配偶ｖ扔进队列的时候，我们把ｕ标记为T型，ｖ标记为S型。于是，搜索树的样子是这样的：
ｓ
／ ＼
ａ ｂ
｜ ｜
ｃ ｄ
／ ＼ ／ ＼
ｅ ｆ ｕ ｊ
｜ ｜ ｜ ｜
ｉ ｊ ｖ ｋ
其中，黑色竖线相连的两个点是已经匹配好的，蓝色斜线表示两个点之间有边，但是没有配对。T型的用红色，S型的用黑色。
这里有个小问题：一个S型点ｄ在某一步扩展的时候发现了点ｕ，如果ｕ已经在搜索树上了（即，出现了环），怎么办？
我们规定，如果ｕ的类型是T型，就无视这次发现；（这意味着我们找到了一个长度为偶数的环，直接无视）
ｓ
／ ＼
ａ ｂ
｜ ｜
ｃ ｄ 如果连出来的边是指向T型点的，就无视这个边。
／ ＼ ／ ＼
ｅ ｆ＜－ ｇ
｜ ｜ ｜
ｉ ｊ ｋ
否则，我们找到了一个长度为奇数的环，就要进行一次“缩花”的操作！所谓缩花操作，就是把这个环缩成一个点。
ｓ
／ ＼
ａ ｂ
｜ ｜
ｃ ｄ
／ ＼ ／ ＼
ｅ ｆ ｜ ｇ
｜ ｜ ｜ ｜
ｉ ｕ＜－＋ ｋ
这个图缩花之后变成了５个点（一个大点，或者叫一朵花，加原来的４个点）：
缩点完成之后，还要把原来环里面的T型点统统变成S型点，之后扔到队列里去。
＋－－－－－－－－－－－－－＋
｜ ｜
｜ ｓ ｜
｜ ／ ＼ ｜
｜ ａ ｂ ｜
｜ ｜ ｜ ｜ 现在是一个点了！还是一个S点。
｜ ｃ ｄ ｜
｜ ／ ＼ ／ ＼ ｜
＋－｜－－ ｆ－－ｕ －－－｜－－－＋
｜ ｜ ｜ ｜
｜ ｜ ｜ ｜
｜ ｜ ｜ ｜
｜ ＋－－－－－－－－－－－－－＋ ｜
｜ ｜
ｅ ｇ
｜ ｜
ｉ ｋ
为什么能缩成一个点呢？我们看一个长度为奇数的环（例如上图中的ｓ－ｂ－ｄ－ｕ－ｆ－ｃ－ａ－），如果我们能够给它中的任意一个点找一个出度（配偶），那么环中的其他点正好可以配成对，这说明，每个点的出度都是等效的。例如，假设我们能够给图中的点ｄ另找一个配偶（例如ｄ＇好了），那么，环中的剩下６个点正好能配成３对，一个不多，一个不少（算上ｄ和ｄ＇一共４对刚刚好）。
ａ－ｓ－ｂ－ｄ－ｄ＇ ａ ｓ－ｂ ｄ－ｄ＇
＼ ｜ ＝＞ ＼
ｃ－ｆ－ｕ ｃ ｆ－ｕ
这就是我们缩点的思想来源。有一个劳苦功高的计算机科学家证明了：缩点之前和缩点之后的图是否有增广路的情况是相同的。
缩起来的点又叫一朵花（ｂｌｏｓｓｏｍ）．
注意到，组成一朵花的里面可能嵌套着更小的花。
当我们最终找到一条增广路的时候，要把嵌套着的花层层展开，还原出原图上的增广路出来。
嗯，现在你对实现这个算法有任何想法吗？
天啊，还要缩点……写死谁。。。。。。
我一开始也是这么想的。
我看了一眼网上某个大牛的程序，之后结合自己的想法，很努力地写出了一个能AC的版本。
实现的要点有什么呢？
首先，我们不“显式”地表示花。我们记录一个Nｅｘｔ数组，表示最终增广的时候的路径上的后继。同时，我们维护一个并查集，表示每个点现在在以哪个点为根的花里（一个花被缩进另一朵花之后就不算花了）。还要记录每个点的标记。
主程序是一段BFS。对于每个由ｘ发展出来的点ｙ，分４种情况讨论：
１。ｘｙ是配偶（不说夫妻，这是非二分图。。。）或者ｘｙ现在是一个点（在一朵花里）：直接无视
２。ｙ是T型点：直接无视
３。ｙ目前单身：太好了，进行增广！
４。ｙ是一个S型点：缩点！缩点！
缩点的时候要进行的工作：
１。找ｘ和ｙ的LCA（的根）ｐ。找LCA可以用各种方法。。。直接朴素也行。
２。在Nｅｘｔ数组中把ｘ和ｙ接起来（表示它们形成环了！）
３。从ｘ、ｙ分别走到ｐ，修改并查集使得它们都变成一家人，同时沿路把Nｅｘｔ数组接起来。
Nｅｘｔ数组很奇妙。每时每刻，它实际形成了若干个挂在一起的双向链表来表示一朵花内部的走法。
－－－－
／ ＼＜－－＋
｜ ｜ ｜
｜ ｜＜－－＋
ｖ ｖ
－－－－－－－－－－
／ ＼
＋－ －－＋
｜ ｜
｜ ｜
＋－－－－＞ｓ ＜－－－－－－＋
代码
#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; const int N = 250; // 并查集维护 int belong[N]; int findb(int x) { return belong[x] == x ? x : belong[x] = findb(belong[x]); } void unit(int a, int b) { a = findb(a); b = findb(b); if (a != b) belong[a] = b; } int n, match[N]; vector<int> e[N]; int Q[N], rear; int next[N], mark[N], vis[N]; // 朴素算法求某阶段中搜索树上两点x, y的最近公共祖先r int LCA(int x, int y) { static int t = 0; t++; while (true) { if (x != -1) { x = findb(x); // 点要对应到对应的花上去 if (vis[x] == t) return x; vis[x] = t; if (match[x] != -1) x = next[match[x]]; else x = -1; } swap(x, y); } } void group(int a, int p) { while (a != p) { int b = match[ a ], c = next[ b ]; // next数组是用来标记花朵中的路径的，综合match数组来用，实际上形成了 // 双向链表，如(x, y)是匹配的，next[x]和next[y]就可以指两个方向了。 if ( findb( c ) != p ) next[ c ] = b; // 奇环中的点都有机会向环外找到匹配，所以都要标记成S型点加到队列中去， // 因环内的匹配数已饱和，因此这些点最多只允许匹配成功一个点，在aug中 // 每次匹配到一个点就break终止了当前阶段的搜索，并且下阶段的标记是重 // 新来过的，这样做就是为了保证这一点。 if (mark[b] == 2) mark[Q[rear++] = b] = 1; if (mark[c] == 2) mark[Q[rear++] = c] = 1; unit(a, b); unit(b, c); a = c; } } // 增广 void aug(int s) { for (int i = 0; i < n; i++) // 每个阶段都要重新标记 next[i] = -1, belong[i] = i, mark[i] = 0, vis[i] = -1; mark[s] = 1; bool falg=false; Q[0] = s; rear = 1; for (int front = 0; match[s] == -1 && front < rear; front++) { int x = Q[front]; // 队列Q中的点都是S型的 for (int i = 0; i < (int)e[x].size(); i++) { int y = e[x][i]; if (match[x] == y) continue; // x与y已匹配，忽略 if (findb(x) == findb(y)) continue; // x与y同在一朵花，忽略 if (mark[y] == 2) continue; // y是T型点，忽略 if (mark[y] == 1) { // y是S型点，奇环缩点 int r = LCA(x, y); // r为从i和j到s的路径上的第一个公共节点 if (findb(x) != r) next[ x ] = y; // r和x不在同一个花朵，next标记花朵内路径 if (findb(y) != r) next[ y ] = x; // r和y不在同一个花朵，next标记花朵内路径 // 将整个r -- x - y --- r的奇环缩成点，r作为这个环的标记节点，相当于论文中的超级节点 group(x, r); // 缩路径r --- x为点 group(y, r); // 缩路径r --- y为点 } else if (match[y] == -1) { // y自由，可以增广，R12规则处理 next[y] = x; for (int u = y; u != -1; ) { // 交叉链取反 int v = next[u]; int mv = match[v]; match[v] = u, match[u] = v; u = mv; } falg=true; break; // 搜索成功，退出循环将进入下一阶段 } else { // 当前搜索的交叉链+y+match[y]形成新的交叉链，将match[y]加入队列作为待搜节点 next[y] = x; mark[Q[rear++] = match[y]] = 1; // match[y]也是S型的 mark[y] = 2; // y标记成T型 } } if(falg) break; } } bool g[N][N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) g[i][j] = false; // 建图，双向边 int x, y; while(scanf("%d%d",&x,&y)==2) { x--, y--; if (x != y && !g[x][y]) e[x].push_back(y), e[y].push_back(x); g[x][y] = g[y][x] = true; } // 增广匹配 for (int i = 0; i < n; i++) match[i] = -1; for (int i = 0; i < n; i++) if (match[i] == -1) aug(i); // 输出答案 int tot = 0; for (int i = 0; i < n; i++) if (match[i] != -1) tot++; printf("%d ", tot); for (int i = 0; i < n; i++) if (match[i] > i) printf("%d %d ", i + 1, match[i] + 1); return 0; }
有权图的最大匹配怎么做？
看论文吧。。。用类似KM的方法，不过，是给每个花再来一个权值。真的很复杂。。。
有一个人写了代码，好像是GPL许可证。。。你最好想办法搜到它的网站来看看版权的问题；总之，我先贴出来：