匈牙利算法(Edmonds算法)步聚：(1)首先用（*）标记X中所有的非M顶点，然后交替进行步骤（2），（3）。
(2)选取一个刚标记（用（*）或在步骤（3）中用（y i）标记）过的X中顶点，例如顶点x，如果x i与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过,则用（x i）i去标记Y中顶点y。
重复步骤(2)，直至对刚标记过的X中顶点全部完成一遍上述过程。
(3)选取一个刚标记（在步骤(2)中用(x i)标记）过的Y中结点，例如y i，如果y i与x为同一匹配边的两端点，且在本步骤中x尚未被标记过，则用(y i)去标记X中结点x。
重复步骤(3)，直至对刚标记过的Y中结点全部完成一遍上述过程。
(2),(3)交替执行，直到下述情况之一出现为止：(I)标记到一个Y中顶点y，它不是M顶点。
这时从y出发循标记回溯，直到（*）标记的X中顶点x，我们求得一条交替链。
设其长度为2k+1，显然其中k条是匹配边，k+1条是非匹配边。
(II)步骤(2)或(3)找不到可标记结点，而又不是情况(I)。
(4)当(2),(3)步骤中断于情况(I)，则将交替链中非匹配边改为匹配边，原匹配边改为非匹配边(从而得到一个比原匹配多一条边的新匹配)，回到步骤(1)，同时消除一切现有标记。
(5)对一切可能,(2)和(3)步骤均中断于情况(II),或步骤(1)无可标记结点,算法终止(算法找不到交替链).以上算法说穿了，就是从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过交替出现。
找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。
不断执行上述操作，直到找不到这样的路径为止。
下面给出此算法的一个例子：（1）置M = 空，对x1-x6标记（*）。
（2）找到交替链（x1, y1）（由标记（x1），（*）回溯得），置M = {(x1, y1)}。
(3)找到交替链（x2, y2）（由标记（x2），（*）回溯得），置M = {(x1, y1), (x2, y2),}。
（4）找到交替链（x3, y1, x1, y4）（如图9.4所示。
图中虚线表示非匹配边，细实线表示交替链中非匹配边，粗实线表示匹配边），因而得M = {(x2, y2), (x3, y1),(x1, y4)}。
（5）找到交替链（x4, y3）（由标记（x4），（*）回溯得），置M = {(x2, y2), (x3, y1), (x1, y4), (x4, y3)}。
（6）找到交替链（x5, y4, x1, y1, x3, y7）（如图9.5所示，图中各种线段的意义同上），因而得M = {(x2, y2), (x4, y3),(x5, y4), (x1, y1), (x3, y 7)}下面是几个练习题：http://172.28.138.8:8080/acmhome/problemdetail.do?&method=showdetail&id=13871387 Guardian of Decency题目给出一些boy和girl，有一些规则他们在一些条件下可能恋爱，求最多有多少人，他们之间不会恋爱，根据这样的规则构建一个二分图：boy和girl分两边,分别作为左右结点，根据规则如果满足可能恋爱的条件就连接，否则不连接，求出最大匹配，N-max_number_of_couples即为要求的结果。
实现代码：#include<iostream>#include<string>#include<cmath>using namespace std;typedef struct{char sex;string str;int height;string sports;}People;People p[505];int n;int px[505],py[505];int map[505][505];int flag[505];int check(int i,int j){if(abs(p[i].height-p[j].height)<=40&&p[i].sex!=p[j].sex&&p[i]pare(p[j].str)==0&&p[ i]pare(p[j].sports)!=0)return 1;return 0;}int Path(int i){int j;px[i]=1;for(j=1;j<=n;j++){if(map[i][j]&&!py[j]){py[j]=1;if(flag[j]==-1||Path(flag[j])){flag[j]=i;return 1;}}}return 0;}void Max_Match(){int i;int Max=0;memset(flag,-1,sizeof(flag));for(i=1;i<=n;i++)px[i]=0;for(i=1;i<=n;i++){memset(py,0,sizeof(py));if(!px[i])Max+=Path(i);}cout<<n-Max/2<<endl;}int main(){int i,j,k;int m;cin>>m;while(m--){cin>>n;for(i=1;i<=n;i++){cin>>p[i].height>>p[i].sex>>p[i].str>>p[i].sports;}memset(map,0,sizeof(map));for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(check(i,j))map[i][j]=1;Max_Match();}return 0;}2730Gopher IIhttp://172.28.138.8:8080/acmhome/problemdetail.do?&method=showdetail&id=2730该题给出m个动物的地点，n个洞，还有速度和时间(其实就是给了距离)，问m个动物最多能有几个在规定的时间里一规定的速度躲到洞里逃生，。
典型的二分图匹配的问题，动物的位置为左边的结点，洞为右边的结点，如果他们的距离小于等于时间×速度，我们就认为他们是连接的，否则认为不连接，我们只要计算最大二分图匹配数，就是可以逃生的动物数，用总数减去匹配数就是不能逃生的，即为所求。
实现代码：#include<iostream>#include<math.h>usingnamespace std;#define Max 101typedefstruct{double x,y;}Node;int map[Max][Max];bool mark[Max];int nx,ny;int cx[Max],cy[Max];Node G[Max],H[Max];int Find_Path(int u){int i;for(i=0;i<ny;i++){if(map[u][i]&&!mark[i]){mark[i]=true;if(cy[i]==-1||Find_Path(cy[i])){cy[i]=u;cx[u]=i;return 1;}}}return 0;}int Max_Match()int res=0;int i,j;for(i=0;i<nx;i++)cx[i]=-1;for(i=0;i<ny;i++)cy[i]=-1;for(i=0;i<nx;i++){if(cx[i]==-1){for(j=0;j<ny;j++)mark[j]=false;res+=Find_Path(i);}}return res;}int main(){int i,j;int s,v;while(cin>>nx>>ny>>s>>v){for(i=0;i<nx;i++)cin>>G[i].x>>G[i].y;for(i=0;i<ny;i++)cin>>H[i].x>>H[i].y;for(i=0;i<nx;i++)for(j=0;j<ny;j++){if(sqrt((((G[i].x-H[j].x)*(G[i].x-H[j].x))+((G[i].y-H[j].y)*(G[i].y-H[j].y))))/v<s)map[i][j]=1;else map[i][j]=0;}cout<<nx-Max_Match()<<endl;}return 0;}1990 Asteroidshttp://172.28.138.8:8080/acmhome/problemdetail.do?&method=showdetail&id=1990题目给出一个矩阵，上面有敌人，每个子弹可以打出一横行或者一竖行，问最少用多少子弹消灭都有敌人，如：X.X.X..X.x表示敌人，显然用两个子弹就可以解决所有敌人。
下面介绍一下二分图的最小点覆盖数：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。
König定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小点覆盖数。
这样，我们可以构建一个这样的二分图，左右边的结点数分别是矩阵的行和列，然后有敌人的地方就连接上(例如第一行第一列有敌人，就连接左边的1和右边的1)，这样，二分图中的每条边就代表一个敌人，我们找到最少的n个点，这n个点能覆盖二分图中的所有边，即是最小点覆盖数，根据König定理，一个二分图中的最大匹配数等于这个图中的最小点覆盖数，所以只要求这样一个二分图的最大二分匹配即可。
实现代码：#include<stdio.h>#include <string.h>#define MAXN 505int uN,vN;bool g[MAXN][MAXN];int xM[MAXN],yM[MAXN];bool chk[MAXN];bool SearchPath(int u){int v;for(v=1;v<=vN;v++)if(g[u][v]&&!chk[v]){chk[v]=true;if(yM[v]==-1||SearchPath(yM[v])){yM[v]=u;xM[u]=v;return true;}}return false;}int MaxMatch(){int u,ret=0;memset(xM,-1,sizeof(xM));memset(yM,-1,sizeof(yM));for(u=1;u<=vN;u++)if(xM[u]==-1){memset(chk,false,sizeof(chk));if(SearchPath(u))ret++;}return ret;}int main(){int i,j,x,y;while(scanf("%d %d",&vN,&uN)!=EOF){for(i=1;i<=vN;i++)for(j=1;j<=vN;j++)g[i][j]=0;for(i=0;i<uN;i++){scanf("%d %d",&x,&y);g[x][y]=1;}printf("%d\n",MaxMatch());}return 0;}1671Girls and Boyshttp://172.28.138.8:8080/acmhome/problemdetail.do?&method=showdetail&id=1671题目给出一些boy和girl，有一些人有罗曼史，比如A和B有罗曼史，那么B和A就有罗曼史，求最多有多少人，他们之间没有罗曼史，根据这样的规则构建一个二分图：boy和girl分两边,分别作为左右结点，根据规则如果有罗曼史就连接，否则不连接，求出最大匹配，N-m ax_num ber_of_couples/2即为要求的结果,因为比如A和B有罗曼史，那么B和A就有罗曼史，所以重复算了一次(在这种情况下A和B去掉一个即可)。