匈牙利算法

（一）首先明确匈牙利算法是干嘛滴？

　　　　匈牙利算法是解决二部图最大匹配问题滴。

（二）算法的核心思想：不断寻找增广路径，每找到一条增广路径，就通过异或操作使匹配边数加一，直到找不到增广路径，算法结束。

（三）算法的基本步骤：

　　　　(1)任取二部图G(X,Y)的匹配M，若M饱和X，则停止。若M不能饱和X，则取X的未标记的M非饱和点x。（标记的点表示经过此点不存在增广路）令S={x},T= Ø.(T集合中的点表示N（S）中已经加入增广路的点）(当不存非饱和点或者所有非饱和点都被标记,算法结束)

　　　　(2)若N(S)=T，（S集合中的所有点的对应项都是已经走过的的点）则返回(1)，即无经过x的增广通路，标记x。否则，取y ∈N(S)-T。

　　　　(3)若y是M饱和的，则存在z ∈X-S使yz ∈M.令S=S∪{z}，T=T∪{y}，转入(2)。若y是M非饱和的，则G中存在以x为起点y为终点的M增广通路P。用令M=M异或EP，即将这条增广路上的已匹配边与未匹配边对换，得到比原来匹配数多一的新匹配，转入(1).

（四）算法的核心结构

 1 void hungary()//匈牙利算法
 2 {
 3     for i->1 to n
 4         if (从i的对应项出有可增广路)
 5             匹配数++;
 6     输出 匹配数;
 7 }
 8 bool  findpath(k)//寻找从k出发的对应项出的可增广路
 9 {
10     while (从邻接表中列举k能关联到顶点j){
11         if (j不在增广路上){
12             把j加入增广路;
13             if (j是未匹配点 或者 从j的对应项出发有可增广路)
14                 修改j的对应项为k;//也就是说边(k,j)匹配，j对应匹配到k上
15                 则从k的对应项出有可增广路,返回true;
16             }
17         }
18     }
19     则从k的对应项出没有可增广路,返回false;
20 }

（五）算法的核心代码

 1 bool findpath(int x)
 2 {
 3     visx[x] = true;
 4     for(int y = 1 ; y <= ny ; ++y){
 5         if(!visy[y] && (lx[x] + ly[y] == G[x][y])){
 6             visy[y] = true;
 7             if(match[y] == -1 || findpath(match[y])){
 8                 match[y] = x;
 9                 return true;
10             }
11         }
12     }
13     return false;
14 }

（六）下面放一道已经AC的题HDU1469

http://poj.org/problem?id=1469

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 #define P 110
 5 #define N 310
 6 int map[P][N];
 7 int match[N];
 8 bool use[N];
 9 int p, n;
10 
11 bool find(int u) //u是课程
12 {
13     for(int i = 1; i <= n; ++i)
14     {
15         if(!use[i] && map[u][i]) //标记匹配的学生
16         {
17             use[i] = true;
18             if(match[i] == - 1 || find(match[i]))
19             {
20                 match[i] = u;
21                 return true;
22             }
23         }
24     }
25     return false;
26 }
27 
28 int sum()
29 {
30     int ans = 0;
31     for(int i = 1; i <= p; ++i) //统计匹配的课程
32     {
33         memset(use, false, sizeof(use));
34         if(find(i))
35             ans++;
36     }
37     return ans;
38 }
39 
40 int main()
41 {
42     int T;
43     int m, temp, ans;
44     scanf("%d", &T);
45     while(T--)
46     {
47         memset(map, 0, sizeof(map));
48         memset(match, -1, sizeof(match));
49         scanf("%d%d", &p, &n);
50         for(int i = 1; i <= p; ++i)
51         {
52             scanf("%d", &m);
53             for(int j = 1; j <= m; ++j)
54             {
55                 scanf("%d", &temp);
56                 map[i][temp] = 1; //j号学生喜欢i号课程
57             }
58         }
59         ans = sum();
60         printf("%s
", ans == p ? "YES" : "NO");
61     }
62     return 0;
63 }

今天刚学完匈牙利算法，趁热打铁，赶快写篇博客加深一下印象！看不懂你打我！！！不认真看打死你！！！