[ACM_图论] 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

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

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

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

置边集M为空（初始化，谁和谁都没连着）
选择一个新的原点寻找增广路
重复(2)操作直到找不出增广路径为止（2，3步骤构成一个循环）

^_^:匈牙利算法过程演示：

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

#include <iostream>
#include <stdlib.h>
#include <memory.h>
using namespace std;
int tab[][];//邻接矩阵,不是真正意义的邻接矩阵,第一维对应牛,第二维对应牛棚
int state[],result[];//stata:是否被搜索过;result:某牛栏对应的牛
int n,m;
int ans;//找到多少匹配 int find(int x){// 匈牙利算法
for(int i=;i<=m;i++){
if(tab[x][i]== && !state[i]){
state[i]=;//标记为搜索过
if(result[i]== || find(result[i])){//未被匹配过&&能找到一条增广路
result[i]=x;//匹配i,x
return ;//能找到新的匹配
}
}
}
return ;
}
int main(){
int n1,t;
cin>>n>>m;
memset(tab,,sizeof(tab));
for(int i=;i<=n;i++){
cin>>n1;
for(int j=;j<=n1;j++){
cin>>t;
tab[i][t]=;
}
}
for(int i=;i<=n;i++){
memset(state,,sizeof(state));//清空是否搜索过数组
if(find(i)) ans++;//找到新的匹配
}//完成后Result[i]保存着第i个牛栏对应的奶牛，本题不用输出，其他题有可能用
cout<<ans<<endl;
return ;
}