題目描述
學(xué)校放假了 · · · · · · 有些同學(xué)回家了，而有些同學(xué)則有以前的好朋友來探訪，那么住宿就是一個(gè)問題。

比如 A 和 B 都是學(xué)校的學(xué)生，A 要回家，而 C 來看B，C 與 A 不認(rèn)識(shí)。我們假設(shè)每個(gè)人只能睡和自己直接認(rèn)識(shí)的人的床。那么一個(gè)解決方案就是 B 睡 A 的床而 C 睡 B 的床。而實(shí)際情況可能非常復(fù)雜，有的人可能認(rèn)識(shí)好多在校學(xué)生，在校學(xué)生之間也不一定都互相認(rèn)識(shí)。

我們已知一共有 n 個(gè)人，并且知道其中每個(gè)人是不是本校學(xué)生，也知道每個(gè)本校學(xué)生是否回家。問是否存在一個(gè)方案使得所有不回家的本校學(xué)生和來看他們的其他人都有地方住。

輸入輸出格式
輸入格式：
第一行一個(gè)數(shù) T 表示數(shù)據(jù)組數(shù)。接下來 T 組數(shù)據(jù)，每組數(shù)據(jù)第一行一個(gè)數(shù)n 表示涉及到的總?cè)藬?shù)。

接下來一行 n 個(gè)數(shù)，第 i 個(gè)數(shù)表示第 i 個(gè)人是否是在校學(xué)生 (0 表示不是，1 表示是)。再接下來一行 n 個(gè)數(shù)，第 i 個(gè)數(shù)表示第 i 個(gè)人是否回家 (0 表示不回家，1 表示回家，注意如果第 i 個(gè)人不是在校學(xué)生，那么這個(gè)位置上的數(shù)是一個(gè)隨機(jī)的數(shù)，你應(yīng)該在讀入以后忽略它)。

接下來 n 行每行 n 個(gè)數(shù)，第 i 行第 j 個(gè)數(shù)表示 i 和 j 是否認(rèn)識(shí) (1 表示認(rèn)識(shí)，0 表示不認(rèn)識(shí)，第 i 行 i 個(gè)的值為 0，但是顯然自己還是可以睡自己的床)，認(rèn)識(shí)的關(guān)系是相互的。

輸出格式：
對(duì)于每組數(shù)據(jù)，如果存在一個(gè)方案則輸出 “^_^”(不含引號(hào)) 否則輸出“T_T”(不含引號(hào))。(注意輸出的都是半角字符，即三個(gè)符號(hào)的 ASCII 碼分別為94,84,95)

輸入輸出樣例
輸入樣例#1：
1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0
輸出樣例#1：

^_^

說明
對(duì)于 30% 的數(shù)據(jù)滿足 1 ≤ n ≤ 12。

對(duì)于 100% 的數(shù)據(jù)滿足 1 ≤ n ≤ 50,1 ≤ T ≤ 20。

多組數(shù)據(jù)！！！
/*
一開始沒有了解二分圖匹配，直接用DFS爆搜,然后只得了90分，有一組測(cè)試數(shù)據(jù)TEL
后來了解了一下二分圖匹配，把之前的代碼稍微改進(jìn)了一下，就AC了
*/

//改進(jìn)后100分code #include <iostream> #include <string.h> #include <vector> using namespace std; struct person {int stu;int goHome; }; vector<int>v1,v2[55]; bool used[55]; int flag,aim; int link[55]; int DFS(int x) {for(int i = 0; i < v2[x].size(); i++){int k = v2[x][i];if(!used[k])//防止匹配到這張床之后（DFS(link[k])）又回到這張床{used[k] = true;if(!link[k]||DFS(link[k]))//這張床沒有主人or這張床有主人了但那個(gè)主人可以去別的床{link[k] = x;//讓這張床的主人為當(dāng)前來匹配的這個(gè)人return 1;}}}return 0; } int main() {int t,x;cin>>t;while(t--){int n;cin>>n;person data[n+5];int sum = 0;for(int i = 1; i <= n; i++){cin>>data[i].stu;if(data[i].stu)sum++;v2[i].clear();}v1.clear();for(int i = 1; i <= n; i++){cin>>data[i].goHome;if((data[i].stu&&!data[i].goHome)||!data[i].stu){v1.push_back(i);}}aim = v1.size();for(int i =1; i <= n; i++){for(int j = 1; j <= n ; j++){cin>>x;if(i==j||x){if(data[j].stu)v2[i].push_back(j);}}}flag = 0;memset(link,0,sizeof(link));if(aim <= sum){int cnt = 0;for(int i = 0; i < v1.size(); i++){memset(used,false,sizeof(used));cnt += DFS(v1[i]);}if(cnt == aim)//最大匹配達(dá)標(biāo)flag = 1;}if(flag)cout<<"^_^"<<endl;elsecout<<"T_T"<<endl;}return 0; } //90分TELcode #include <iostream> #include <string.h> #include <vector> using namespace std; struct person {int stu;int goHome; }; vector<int>v1,v2[55]; bool used[55]; int a[55][55],flag,aim; void DFS(int now,int cnt) {if(aim-now > cnt)return;if(now == aim){flag = 1;return;}if(!flag){for(int i = 0; i < v2[v1[now]].size(); i++){int k = v2[v1[now]][i];if(!used[k]){used[k] = true;DFS(now+1,cnt-1);used[k] = false;}}return;} } int main() {int t;cin>>t;while(t--){int n;cin>>n;person data[n+5];int sum = 0;for(int i = 1; i <= n; i++){cin>>data[i].stu;if(data[i].stu)sum++;v2[i].clear();}v1.clear();for(int i = 1; i <= n; i++){cin>>data[i].goHome;if((data[i].stu&&!data[i].goHome)||!data[i].stu){v1.push_back(i);}}aim = v1.size();for(int i =1; i <= n; i++){for(int j = 1; j <= n ; j++){cin>>a[i][j];if(i==j||a[i][j]){if(data[j].stu)v2[i].push_back(j);}}}flag = 0;memset(used,false,sizeof(used));if(aim <= sum)DFS(0,sum);if(flag)cout<<"^_^"<<endl;elsecout<<"T_T"<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P2055 [ZJOI2009]假期的宿舍（二分图匹配）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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