The Perfect Stall 完美的牛栏(匈牙利算法、最大二分匹配)

描述

农夫约翰上个星期刚刚建好了他的新牛棚,他使用了最新的挤奶技术。不幸的是,由于工程问题,每个牛栏都不一样。第一个星期,农夫约翰随便地让奶牛们进入牛栏,但是问题很快地显露出来:每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期,农夫约翰刚刚收集到了奶牛们的爱好的信息(每头奶牛喜欢在哪些牛栏产奶)。一个牛栏只能容纳一头奶牛,当然,一头奶牛只能在一个牛栏中产奶。

给出奶牛们的爱好的信息,计算最大分配方案。

格式

PROGRAM NAME: stall4

INPUT FORMAT:

(file stall4.in)

第一行 两个整数,N (0 <= N <= 200) 和 M (0 <= M <= 200) 。N 是农夫约翰的奶牛数量,M 是新牛棚的牛栏数量。

第二行到第N+1行 一共 N 行,每行对应一只奶牛。第一个数字 (Si) 是这头奶牛愿意在其中产奶的牛栏的数目 (0 <= Si <= M)。后面的 Si 个数表示这些牛栏的编号。牛栏的编号限定在区间 (1..M) 中,在同一行,一个牛栏不会被列出两次。

OUTPUT FORMAT:

(file stall4.out)

只有一行。输出一个整数,表示最多能分配到的牛栏的数量.

SAMPLE INPUT

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

SAMPLE OUTPUT

4


^_^:本文参阅http://comzyh.tk/blog/archives/148/  COMZYH的博客(不错的博客哦!推荐)

^_^:解决最大二分匹配问题可以用网络流的最大流实现,不过最大流比较复杂,使用匈牙利算法编程较简单:

^_^:匈牙利算法核心思路: 

  1. 置边集M为空(初始化,谁和谁都没连着)
  2. 选择一个新的原点寻找增广路
  3. 重复(2)操作直到找不出增广路径为止(2,3步骤构成一个循环)
^_^:匈牙利算法过程演示:

The Perfect Stall 完美的牛栏(匈牙利算法、最大二分匹配)

  1. 初始化(清空)
  2. 从A所连接的点中找到一个未在本次循环中搜索过的点2,并将2标记为搜索过,因为2没有被连接过,匹配A2
  3. 结束上次,开始新的循环,将所有点标记为未搜索过
  4. 搜索B,找到一个未在本次循环中搜索过的点2,标记为搜索过
  5. 发现2被匹配过,从2的父亲A寻找增广路,递归搜索A{从A所连接的点中找到一个未在本次循环中搜索过的点5(1已经标记为绿色),将5标记为搜索过,因为5没有被匹配过,匹配A5}找到增广路(此处为增广路的关键
  6. 结束上次,开始新的循环,将所有点标记为未搜索过
  7. 搜索C,找到一个未在本次循环中搜索过的点1,并将1标记为搜索过,发现1未被匹配过,匹配C1
  8. 结束上次,开始新的循环,将所有点标记为未搜索过
  9. 搜索D,找到一个未在本次循环中搜索过的点1,并将1标记为搜索过,发现1被匹配过,递归搜索1的源C寻找增广路
  10. {搜索C,找到一个未在本次循环中搜索过的点5,标记为搜索过,发现5被匹配,进一步返现没有其他可连接点,返回找不到增广路}返回第9步
  11. 搜索D,找到一个未在本次循环中搜索过的点2,发现2被匹配,递归搜索2的源B寻找增广路
  12. {搜索B,找到一个未在本次循环中搜索过的点3,并将3标记为搜索过,发现3未被匹配,匹配B3返回找到}既然B另寻新欢,匹配D2
  13. 结束上次,开始新的循环,将所有点标记为未搜索过,递归搜索D寻找增广路
  14. 搜索E,找到一个未在本次循环中搜索过的点2,并将2标记为搜索过,发现2被匹配过,递归搜索2的源D寻找增广路
  15. {搜索D,发现1,5均被匹配过,返回找不到增广路}
  16. E无其他可连接节点,放弃E,E后无后续节点,已经遍历A-E,结束算法

 

The Perfect Stall 完美的牛栏(匈牙利算法、最大二分匹配)
 1 #include <iostream>
 2 #include <stdlib.h>
 3 #include <memory.h>
 4 using namespace std;
 5 int tab[201][201];//邻接矩阵,不是真正意义的邻接矩阵,第一维对应牛,第二维对应牛棚
 6 int state[201],result[201];//stata:是否被搜索过;result:某牛栏对应的牛
 7 int n,m;
 8 int ans;//找到多少匹配
 9  
10 int find(int x){// 匈牙利算法
11     for(int i=1;i<=m;i++){
12         if(tab[x][i]==1 && !state[i]){
13            state[i]=1;//标记为搜索过
14            if(result[i]==0 || find(result[i])){//未被匹配过&&能找到一条增广路
15               result[i]=x;//匹配i,x
16               return 1;//能找到新的匹配
17            }
18         }
19     }
20     return 0;
21 }
22 int main(){
23     int n1,t;
24     cin>>n>>m;
25     memset(tab,0,sizeof(tab));
26     for(int i=1;i<=n;i++){
27         cin>>n1;
28         for(int j=1;j<=n1;j++){
29             cin>>t;
30             tab[i][t]=1;
31         }
32     }
33     for(int i=1;i<=n;i++){
34         memset(state,0,sizeof(state));//清空是否搜索过数组
35         if(find(i)) ans++;//找到新的匹配
36     }//完成后Result[i]保存着第i个牛栏对应的奶牛,本题不用输出,其他题有可能用
37     cout<<ans<<endl;
38     return 0;
39 }
The Perfect Stall 完美的牛栏(匈牙利算法、最大二分匹配)

The Perfect Stall 完美的牛栏(匈牙利算法、最大二分匹配)

上一篇:【.Net Micro Framework PortingKit(补) – 1】USB驱动开发


下一篇:一个简单的异步处理程序