今天介绍 匈牙利算法 ： 匈牙利算法，是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，由匈牙利数学家Edmonds于1965年提出，因而得名。
先介绍一下增广路径：若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。文字难以理解，看图：
首先 假设 图G中已经两两匹配了4个点 即 M 中 又 （1，A）（4，C）两条边；
然后路径p是一条连接未匹配点2和D的一条路径 其中属于M的边和不属于M的边交错：（2-A-1-C-4-D）,这样就称p为M的一条增广路径；
增广路径的性质：
1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
2－不断寻找增广路可以得到一个更大的匹配M’，直到找不到更多的增广路。
3－M为G的最大匹配当且仅当不存在M的增广路径。
4－最大匹配数M+最大独立数N=总的结点数。
我们将P中不属于M的路径加入M，将原来属于M的路径去除。M的匹配数增加到了 3，如果我们一只找M的增广路径然后取反，直到M没有增广路，这时我们就找到了M的最大匹配数，这也时 匈牙利算法的核心所在；
匈牙利算法 ：首先向M中增加一条路径，然后一只寻找M的增广路径直到M中不存在增广路径为止，这时我们就完成了最大匹配的寻找。
用一个问题来展现匈牙利算法：
假设有一群人生了不同的病（一个人只能生一种病），这里有多种可以治病的药丸，并且一种药丸只能治一种病且仅有一个，问最多能救治多少人；
输入 ：在第一行中给出 n ，m, k 其中 n是人数，m 是 药的种类数，k是 人和药共有多少种匹配，然后 跟着 k 行，每行 一个 整数：人的标号，一个字符 ：药的种类。
输出：在一行中输出最多可以救治多少人。
代码：
//二分图最大匹配-匈牙利算法
#include<stdio.h>
#include<string.h>
#define MAXN 100 //定义最大人数
#define TYPE 6 //定义药的种类数
int map[MAXN][MAXN]; //用来储存人和药的关系
int vis[MAXN]; //用来标记药的被使用人
int used[MAXN]; //用在递归的时候标记修改的药的种类
char array[6] = {'a','b','c','d','e','f'};
int GetPos(char x){ //获取药的索引 int i, position;for (i=0;i<TYPE;i++){if (array[i] == x)return i; // 找到的话就返回索引 }return -1; // 找不到就返回-1
}
void init(){ // 初始化函数 memset(map,-1,sizeof(map));memset(vis,-1,sizeof(vis));memset(used,-1,sizeof(used));
}
int MaxMatch(int n){ // n是人的代号 int i;for (i=0;i<TYPE;i++){if ( used[i]==-1 && map[n][i]==1) //寻找增广路 {used[i] = 1; if (vis[i] == -1||MaxMatch(vis[i])==1){vis[i] = n;return 1;}}}return -1;
}
int main (){int n, m, i, k, cnt = 0, b, index;//n是患病的人数，m是药的种类数，i是循环变量，k是人和药对应关系的数量，cnt记录最大匹配数，b是某人的代号,index记录药的位置 char a; //a是药的品种 scanf("%d%d%d",&n,&m,&k);init();for (i=0;i<k;i++){scanf("%d %c",&b,&a);index = GetPos(a);map[b][index] = 1;}for (i=1;i<=n;i++){memset(used,-1,sizeof(used));//每次都要初始化一遍 每次寻找增广路都与之前无关 if (MaxMatch(i)==1)cnt++;}printf("%d\n",cnt);
}
