Description
Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and, of course, a cow may be only assigned to one stall.
Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.
Input
The input includes several cases. For each case, the first line contains two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. Each of the following N lines corresponds to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow.
Output
For each case, output a single line with a single integer, the maximum number of milk-producing stall assignments that can be made.
Sample Input
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
Sample Output
4
Source
先介紹一些二分圖的基本概念：
二分圖
二分圖是圖論中的一種特殊模型。
設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯(lián)的兩個頂點i和j分別屬于這兩個不同的頂點集(i∈A,j∈B)，則稱圖G為一個二分圖。
如圖就是一個二分圖。
二分圖的匹配
給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。
選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximal matching problem)
如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。
求二分圖最大匹配可以用最大流或者匈牙利算法。
最大匹配
給定一個二分圖G,在G的一個子圖M中,M的邊集中的任意兩條邊都不依附于同一個頂點,則稱M是一個匹配。
選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximal matching problem)
如果一個匹配中,圖中的每個頂點都和圖中某條邊相關聯(lián),則稱此匹配為完全匹配,也稱作完備匹配。
匈牙利算法
求最大匹配的一種顯而易見的算法是:先找出全部匹配,然后保留匹配數(shù)最多的.但是這個算法的復雜度為邊數(shù)的指數(shù)級函數(shù).因此,需要尋求一種更加高效的算法。
增廣路的定義(也稱增廣軌或交錯軌)：
若P是圖G中一條連通兩個未匹配頂點的路徑,并且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn),則稱P為相對于M的一條增廣路徑。
由增廣路的定義可以推出下述三個結論：
1-P的路徑長度必定為奇數(shù),第一條邊和最后一條邊都不屬于M.。
2-P經過取反操作可以得到一個更大的匹配M'。
3-M為G的最大匹配當且僅當不存在相對于M的增廣路徑。
引用Matrix67大牛blog上的一句話概括下求二分圖最大匹配的匈牙利算法：從二分圖中找出一條路徑來，讓路徑的起點和終點都是還沒有匹配過的點，并且路徑經過的連線是一條沒被匹配、一條已經匹配過，再下一條又沒匹配這樣交替地出現(xiàn)。找到這樣的路徑后，顯然路徑里沒被匹配的連線比已經匹配了的連線多一條，于是修改匹配圖，把路徑里所有匹配過的連線去掉匹配關系，把沒有匹配的連線變成匹配的，這樣匹配數(shù)就比原來多1個。不斷執(zhí)行上述操作，直到找不到這樣的路徑為止。
從上面這段話，可以構造出匈牙利算法的算法輪廓：
bool 尋找從k出發(fā)的對應項出的可增廣路
{
while(j與k鄰接){
if(j不在增廣路上){
把j加入增廣路;
if(j是未蓋點 或者 從j的對應項出發(fā)有可增廣路)
則從k的對應項出有可增廣路,返回true;
修改j的對應項為k;
}
}
從k的對應項出沒有可增廣路,返回false;
}
void 匈牙利hungary(){
for i->1 to n{
if(則從i的對應項出有可增廣路)
匹配數(shù)++;
}
輸出 匹配數(shù);
} 然后引入幾個數(shù)據結構：adj為圖的鄰接表，visit[i]記錄點i是否被掃描（匹配）過，match[i]存儲了匹配的方案（點集Y中的點i匹配X中的match[i]，初始值為-1）。
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 201;
bool visit[MAXN];
int n,m,mark[MAXN];
vector< vector<int> > adj;
bool dfs(int pos){
int i,j,pre,len=adj[pos].size();
for(i=0;i<len;i++){
j=adj[pos][i];
if(!visit[j]){
visit[j]=true,pre=mark[j],mark[j]=pos;
if(pre==-1 || dfs(pre))
return true;
mark[j]=pre;
}
}
return false;
}
int hungary(){
int i,ans=0;
for(i=1;i<=n;i++){
memset(visit,false,sizeof(visit));
if(dfs(i)) ans++;
}
return ans;
}
int main(){
int i,j,t;
while(scanf("%d %d",&n,&m)!=EOF){
memset(mark,-1,sizeof(mark));
adj.assign(n+1,vector<int>());
for(i=1;i<=n;i++){
scanf("%d",&t);
while(t--){
scanf("%d",&j);
adj[i].push_back(j);
}
}
printf("%d\n",hungary());
}
return 0;
}