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
先介紹一些二分圖的基本概念：
二分圖
二分圖是圖論中的一種特殊模型。
設(shè)G=(V,E)是一個(gè)無向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j分別屬于這兩個(gè)不同的頂點(diǎn)集(i∈A,j∈B)，則稱圖G為一個(gè)二分圖。
如圖就是一個(gè)二分圖。
二分圖的匹配
給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。
選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximal matching problem)
如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。
求二分圖最大匹配可以用最大流或者匈牙利算法。
最大匹配
給定一個(gè)二分圖G,在G的一個(gè)子圖M中,M的邊集中的任意兩條邊都不依附于同一個(gè)頂點(diǎn),則稱M是一個(gè)匹配。
選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximal matching problem)
如果一個(gè)匹配中,圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián),則稱此匹配為完全匹配,也稱作完備匹配。
匈牙利算法
求最大匹配的一種顯而易見的算法是:先找出全部匹配,然后保留匹配數(shù)最多的.但是這個(gè)算法的復(fù)雜度為邊數(shù)的指數(shù)級函數(shù).因此,需要尋求一種更加高效的算法。
增廣路的定義(也稱增廣軌或交錯(cuò)軌)：
若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑,并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn),則稱P為相對于M的一條增廣路徑。
由增廣路的定義可以推出下述三個(gè)結(jié)論：
1-P的路徑長度必定為奇數(shù),第一條邊和最后一條邊都不屬于M.。
2-P經(jīng)過取反操作可以得到一個(gè)更大的匹配M'。
3-M為G的最大匹配當(dāng)且僅當(dāng)不存在相對于M的增廣路徑。
引用Matrix67大牛blog上的一句話概括下求二分圖最大匹配的匈牙利算法：從二分圖中找出一條路徑來，讓路徑的起點(diǎn)和終點(diǎn)都是還沒有匹配過的點(diǎn)，并且路徑經(jīng)過的連線是一條沒被匹配、一條已經(jīng)匹配過，再下一條又沒匹配這樣交替地出現(xiàn)。找到這樣的路徑后，顯然路徑里沒被匹配的連線比已經(jīng)匹配了的連線多一條，于是修改匹配圖，把路徑里所有匹配過的連線去掉匹配關(guān)系，把沒有匹配的連線變成匹配的，這樣匹配數(shù)就比原來多1個(gè)。不斷執(zhí)行上述操作，直到找不到這樣的路徑為止。
從上面這段話，可以構(gòu)造出匈牙利算法的算法輪廓：
bool 尋找從k出發(fā)的對應(yīng)項(xiàng)出的可增廣路
{
while(j與k鄰接){
if(j不在增廣路上){
把j加入增廣路;
if(j是未蓋點(diǎn) 或者 從j的對應(yīng)項(xiàng)出發(fā)有可增廣路)
則從k的對應(yīng)項(xiàng)出有可增廣路,返回true;
修改j的對應(yīng)項(xiàng)為k;
}
}
從k的對應(yīng)項(xiàng)出沒有可增廣路,返回false;
}
void 匈牙利hungary(){
for i->1 to n{
if(則從i的對應(yīng)項(xiàng)出有可增廣路)
匹配數(shù)++;
}
輸出 匹配數(shù);
} 然后引入幾個(gè)數(shù)據(jù)結(jié)構(gòu)：adj為圖的鄰接表，visit[i]記錄點(diǎn)i是否被掃描（匹配）過，match[i]存儲了匹配的方案（點(diǎn)集Y中的點(diǎn)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;
}