描述

農(nóng)夫約翰上個星期剛剛建好了他的新牛棚，他使用了最新的擠奶技術(shù)。不幸的是，由于工程問題，每個牛欄都不一樣。第一個星期，農(nóng)夫約翰隨便地讓奶牛們進入牛欄，但是問題很快地顯露出來：每頭奶牛都只愿意在她們喜歡的那些牛欄中產(chǎn)奶。上個星期，農(nóng)夫約翰剛剛收集到了奶牛們的愛好的信息（每頭奶牛喜歡在哪些牛欄產(chǎn)奶）。一個牛欄只能容納一頭奶牛，當(dāng)然，一頭奶牛只能在一個牛欄中產(chǎn)奶。

給出奶牛們的愛好的信息，計算最大分配方案。

格式

PROGRAM NAME: stall4

INPUT FORMAT:

(file stall4.in)

第一行 兩個整數(shù)，N (0 <= N <= 200) 和 M (0 <= M <= 200) 。N 是農(nóng)夫約翰的奶牛數(shù)量，M 是新牛棚的牛欄數(shù)量。

第二行到第N+1行 一共 N 行，每行對應(yīng)一只奶牛。第一個數(shù)字 (Si) 是這頭奶牛愿意在其中產(chǎn)奶的牛欄的數(shù)目 (0 <= Si <= M)。后面的 Si 個數(shù)表示這些牛欄的編號。牛欄的編號限定在區(qū)間 (1..M) 中，在同一行，一個牛欄不會被列出兩次。

OUTPUT FORMAT:

(file stall4.out)

只有一行。輸出一個整數(shù)，表示最多能分配到的牛欄的數(shù)量.

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的博客（不錯的博客哦！推薦）

^_^:解決最大二分匹配問題可以用網(wǎng)絡(luò)流的最大流實現(xiàn)，不過最大流比較復(fù)雜，使用匈牙利算法編程較簡單：

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

置邊集M為空（初始化，誰和誰都沒連著）

選擇一個新的原點尋找增廣路

重復(fù)(2)操作直到找不出增廣路徑為止（2，3步驟構(gòu)成一個循環(huán)）

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

初始化（清空）

從A所連接的點中找到一個未在本次循環(huán)中搜索過的點2，并將2標(biāo)記為搜索過，因為2沒有被連接過，匹配A2

結(jié)束上次，開始新的循環(huán)，將所有點標(biāo)記為未搜索過

搜索B，找到一個未在本次循環(huán)中搜索過的點2，標(biāo)記為搜索過

發(fā)現(xiàn)2被匹配過，從2的父親A尋找增廣路，遞歸搜索A{從A所連接的點中找到一個未在本次循環(huán)中搜索過的點5（1已經(jīng)標(biāo)記為綠色），將5標(biāo)記為搜索過，因為5沒有被匹配過，匹配A5}找到增廣路（此處為增廣路的關(guān)鍵）

結(jié)束上次，開始新的循環(huán)，將所有點標(biāo)記為未搜索過

搜索C，找到一個未在本次循環(huán)中搜索過的點1，并將1標(biāo)記為搜索過,發(fā)現(xiàn)1未被匹配過，匹配C1

結(jié)束上次，開始新的循環(huán)，將所有點標(biāo)記為未搜索過

搜索D，找到一個未在本次循環(huán)中搜索過的點1，并將1標(biāo)記為搜索過，發(fā)現(xiàn)1被匹配過，遞歸搜索1的源C尋找增廣路

{搜索C，找到一個未在本次循環(huán)中搜索過的點5，標(biāo)記為搜索過，發(fā)現(xiàn)5被匹配，進一步返現(xiàn)沒有其他可連接點，返回找不到增廣路}返回第9步

搜索D，找到一個未在本次循環(huán)中搜索過的點2，發(fā)現(xiàn)2被匹配，遞歸搜索2的源B尋找增廣路

{搜索B，找到一個未在本次循環(huán)中搜索過的點3，并將3標(biāo)記為搜索過，發(fā)現(xiàn)3未被匹配，匹配B3返回找到}既然B另尋新歡，匹配D2

結(jié)束上次，開始新的循環(huán)，將所有點標(biāo)記為未搜索過，遞歸搜索D尋找增廣路

搜索E，找到一個未在本次循環(huán)中搜索過的點2，并將2標(biāo)記為搜索過，發(fā)現(xiàn)2被匹配過，遞歸搜索2的源D尋找增廣路

{搜索D，發(fā)現(xiàn)1，5均被匹配過，返回找不到增廣路}

E無其他可連接節(jié)點，放棄E，E后無后續(xù)節(jié)點，已經(jīng)遍歷A-E，結(jié)束算法

?

1 #include <iostream> 2 #include <stdlib.h> 3 #include <memory.h> 4 using namespace std; 5 int tab[201][201];//鄰接矩陣,不是真正意義的鄰接矩陣,第一維對應(yīng)牛,第二維對應(yīng)牛棚 6 int state[201],result[201];//stata:是否被搜索過;result:某牛欄對應(yīng)的牛 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;//標(biāo)記為搜索過 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));//清空是否搜索過數(shù)組 35 if(find(i)) ans++;//找到新的匹配 36 }//完成后Result[i]保存著第i個牛欄對應(yīng)的奶牛，本題不用輸出，其他題有可能用 37 cout<<ans<<endl; 38 return 0; 39 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zjutlitao/p/3528203.html

總結(jié)

以上是生活随笔為你收集整理的[ACM_图论] The Perfect Stall 完美的牛栏（匈牙利算法、最大二分匹配）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。