前言：高中时候老师讲这个就听得迷迷糊糊，有一晚花了通宵看KM的Pascal代码，大概知道过程了，后来老师说不是重点，所以忘的差不多了。都知道二分图匹配是个难点，我这周花了些时间研究了一下这两个算法，总结一下1.基本概念M代表匹配集合未盖点：不与任何一条属于M的边相连的点交错轨：属于M的边与不属于M的边交替出现的轨（链）可增广轨：两端点是未盖点的交错轨判断M是最大匹配的标准：M中不存在可增广轨2.最大匹配，匈牙利算法时间复杂度：O(|V||E|)原理：寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。修改M为M&P。即这条轨进行与M进行对称差分运算。所谓对称差分运算，就是比如X和Y都是集合，X&Y=(X并Y)-(x交Y)有一个定理是：M&P的边数是|M|+1，因此对称差分运算扩大了M实现：关于这个实现，有DFS和BFS两种方法。先列出DFS的代码，带注释。这段代码来自中山大学的教材核心部分在dfs(x)，来寻找可增广轨。如果找到的话，在Hungarian()中，最大匹配数加一。这是用了刚才提到的定理。大家可以想想初始状态是什么，又是如何变化的viewplaincopytoclipboardprint?1.#include2.#defineF(i,a,b)for(inti=a;i<=b;i++)3.#definemaxn10024.usingnamespacestd;5.boolmk[maxn],map[maxn][maxn];6.intmatch[maxn],n,m;7.booldfs(intx)//寻找增广链,true表示找到8.{9.for(inti=1;i<=m;i++)10.{11.if(map[x][i]&&!mk[i])12.{13.mk[i]=true;14.intt=match[i];15.match[i]=x;16.if(t==0||dfs(t))17.returntrue;18.match[i]=t;19.}20.}21.returnfalse;22.}23.inthungarian()24.{25.intmax_=0;26.F(i,1,n)27.{28.memset(mk,false,sizeof(mk));29.if(dfs(i))30.max_++;31.}32.returnmax_;33.}34.intmain()35.{36.freopen("in.txt","r",stdin);37.memset(map,false,sizeof(map));38.cin>>n>>m;39.inta,b;40.while(cin>>a>>b)41.{42.map[a][b]=true;43.}44.cout<
