一般图的匹配

1、先来回忆一下我们的匈牙利算法，它是通过DFS找出了一颗“匈牙利树”。我的画图不好请 见谅，图中的直线是有边相连，而折线是匹配边。匈牙利树就是这样一颗交错的树。接着，我们把树上的所有点都分成内点和外点，（奇数为内点，偶数为外点）。每次搜索，我们都是从一个外点(一个非饱和的顶点)出发去搜索。显然若增广树的树叶又连着一个非饱和点，可以看成内点，就可以翻转该路径一个很显然的问 题是：在DFS的过程中，会不会出现圈呢？当然会，但这些圈是可以被忽略的。请看下图，因为二分图的特殊性，圈的出现一定是从一个外点连到内 点。二分图中某点存在一个回路则该回路一定是偶圈，即任以一个点为树根的增广树中，每个点要么是内点

2、，要么是外点，因为唯一能改变其内外点性质的只能是存在回路，若是偶圈显然也不会影响但这并无影响， 因为在这个圈必然是偶数条边，换句话说，圈里本来是内点的点还是内点，本来是外点的点还是外点，因此这个圈是没有作用的。这就是匈牙利算法为什么是正确的。但在一般图中， 就没有这么简单了。来看这个图，1点和2点都是外点，但它们之间却有一条边，这就出现了问题，因为这个圈含有的边数是奇数条！为什么在增广树中出现一个点既是外点又是内点有问题？在二分图中任意一棵增广树中一个点的内外性已确定，因而从树根出发增广路的有无也是确定的，但是在一般图中出现了一个点既是外点又是内点，显然此时增广路还未搜索到，否则已经完成了此次

3、增广路的搜索，那么对之后的搜索会发生错误，因为之后的点不能再确定为内外，必须采取某种措施使得以后的点内外性一致这就是说，在圈上的点（除了跟之外），既是外点也是内点！就是说，本来我们是不能去从那些内点出发去搜索的，但现在可以了，因为只要从圈的另外一边 走过来它就是外点了。搜索时采用广搜的方法寻找增广路径，而且与顶点之间的标号顺序有关21首先从1开始广搜1-2,1-3，先找到2就有匹配边1-2后2是饱和点就跳过，3-1,3-2标记增广树的父节点3-1-2发现遇到了奇圈，就把整个奇圈收缩成一个花34所谓的带花树算法就是，把整个圈缩成一个点，Edmonds称这个超级点为“花”，就是说，原圈里的所有点都

4、作为外点，然后继续搜索。再之后的过程中，已经被缩的点还可能被嵌套地收缩。当我们找到一条增广路之后，还要把路上的“花”展开。总之，带花树的算法思想就是缩点-继续找增广路-找到之后把花展开。这个算法的思想并不难理解、难的是实现。这是网上搜到的Amber写的URAL 1099的程序，我看了很久终于看懂了，我想我也写不出更好的。标程就用他的吧。算法的大体是一个BFS，因为我们在缩点会有一些内点变成外点，因此用BFS更容易把这些点加入到搜索序列中。缩点时所有点都相当于外点程序里别的没什么，难点就是对“花”的操作。用basei表示点i属于哪朵花，这是很精髓的一点就是用到了并查集的思想：把跟作为一个集合的表

5、示。因为虽然有很多圈，但在缩点之后，仍然是一棵树，一棵带着花的树，因此做的时候还是当成树去做。下面开始解释程序：当外点u搜到了外点v之后，要进行BlossomContract先找到u和v的CommonAncestor，找到u和v的最近的公共祖先（外点），这个公共祖先就是这朵新花的跟，然后对u和v分别进行ResetTrace，从u和v出发一路往上走到公共祖先的地方，即以u，v分别作为内点向上走，将原来所有的外点作为补圈的内点边走边把匈牙利树中有向的父子关系改成无向的，但要注意和跟所在花里的点的父子关系不能是无向的。不然会出现绕圈子死循环的情况。同时把路上经过的花也记录下来，把它们的base设成新

6、的公共祖先，做成一朵新的花。最后把u,v之间的父子关系改成无向，同样和跟所在花里的点的父子关系不能是无向的，理由同上。花中任何一点和根不能是无向的关系，即发生两点互指的情形，内部是两点互指的。1147362519101281314匹配边10-9,1-2，3-4,5-6,7-8从11开始增广后一旦找到奇圈，则将奇圈所有的点都看成外点，那么凡是同奇圈相连的点都可以开始搜索，例如和1,2,3,4,5,6,7,8相连的点都行13-5-6-7-8-4-3-2-1-9-10-11构成一条增广路，通过补圈改变了后续的内外性质，和原来的从源点都花根的内外性一致，14-6-5-9-10-11构成一条增广路，仍然

7、采用原来从源点到花根的内外性#include using std: cin;using std: cout;using std: endl;int g250250, match250, inque250, finish, que250, head, tail, father250, n, base250, inblossom250,ans;/basei表明i属于那朵花，并查集int pop() return quehead+;int push(int i) que+tail = i;inquei = 1;return 0;int findancestor(int u, int v)int in

8、path250;for (int i = 1; i = n; i+) inpathi = 0;while (u) u = baseu;/通过并查集来记录新花的树根，当把奇圈压缩成一个顶点后这个顶点可能在和其他的顶点由构成奇圈inpathu = 1;u = fathermatchu;while (v) v = basev;/在找花根时用等效if (inpathv) return v;/找到此时增广树的离u、v最近的外点v = fathermatchv;void reset(int u, int anc) while (u != anc) int v = matchu;inblossombasev

9、 = 1;/若涉及对外访问则等效inblossombaseu = 1;v = fatherv;if (basev != anc) fatherv = matchu;/外点指向内点，内部进行了逆向，使用了原来未利用的外点father域/若涉及内部调整则用其真实的标号u = v;void contract(int u, int v)/u是外点，v本来是内点但由于奇圈变成了外点，也是就u，v都是外点static int num=0;printf(visit here %dn,num+);/最近公共祖先相当于从增广树树根开始第一个接触到该奇圈的点int anc = findancestor(u, v)

10、;/从start开始向外开始的增广树中找到u、v的最最接近的公共祖先for (int i = 1; i u-v？貌似ans一定是u，但又是可能是花中套花，多层嵌套reset(v, anc);if (baseu != anc) /若出现了要压缩奇圈，则仅考虑奇圈其内部一定是最大匹配fatheru = v;if (basev != anc) /basei是i的等效结点，在合并花时奇圈内所有点都被等效成花根fatherv = u;for (int i = 1; i = n; i+) if (inblossombasei) basei = anc;/并查集路径压缩将奇圈内部的点全都看成花根if (!i

11、nquei) /奇圈内所有的点都作为外点，就算以后找到的增广路穿越奇圈内部，在奇圈内部内点指向了外点，外点指向了内点push(i);/遍历时只有visiti=true而没有解除visiti=false是因为对于奇圈内部相对于增广树树根是外点的点/若存在连在奇圈外部的非匹配边，可以在第一次访问到该点后通过广搜就能找到该非匹配边，之后翻转/没有必要等到之后发现是奇圈后在重新遍历，而对于原来相对树根是内点的点来说则是新的搜索起点void findaugment(int start) for (int i = 1; i = n; i+) fatheri = 0;inquei = 0;basei = i

12、;head = 1;tail = 1;que1 = start;inquestart = 1;while (head = tail) int u = pop();/队列中的点都是外点for (int v = 1; v 内点-外点的跳跃fatherv = u;/内点的父亲为外结点else fatherv = u;/内点未被匹配，找到了一条增广路finish = v;return;void augment() int u = finish, v, w;/finish代表内点while (u) v = fatheru;/在增广树中fatherv=u表示u-v的非匹配边w = matchv;/原来的匹配边，又充当逆向到增广树树根的媒介matchu = v;/新添的匹配边matchv = u;/改变原来外点的匹配边u = w;int main()while(cin n)for (int i = 1; i = n; i+) matchi = 0;for (int j = 1; j cnt;while (cnt-) cin kk ll;gkkll = 1;gllkk