題目鏈接：

https://www.luogu.org/problemnew/show/P2055

分析：

這道題比較簡單，二分圖的練習(xí)題（當(dāng)然最大流同理）。

易得我們可以將人放在一側(cè)，床放在一側(cè)。

A與B認(rèn)識就互相向?qū)Ψ降拇策B邊流量為1

A不回家則S向A連流量為1的邊。

A有床則向T連流量為1的邊。

跑最大流即可。

最后判斷是否等于不回家的人數(shù)。

然鵝因?yàn)樽髡咻^懶，于是寫了二分圖，大家可以兩種方法都看看。

代碼：

#include<cstdio> #include<vector> #include<cstring> using namespace std; vector<int>v[20005]; int vis[20005],link[20005]; int t; int a[55],b[55]; int find(int x) {for(int i=0;i<v[x].size();i++){int p=v[x][i];if(vis[p]!=t){vis[p]=t;if((!link[p])||find(link[p])){link[p]=x;return 1;} }}return 0; } int main() {int T;scanf("%d",&T);while(T--){memset(link,0,sizeof(link));int n;scanf("%d",&n);for(int i=1;i<=n;i++){v[i].clear();} for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){scanf("%d",&b[i]);if(b[i]==0&&a[i]){v[i].push_back(i);}}int cnt=0;for(int i=1;i<=n;i++){if(!a[i]||(a[i]&&!b[i]))cnt++;}int tmp;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&tmp);if(tmp&&a[j]){v[i].push_back(j);}}}int tot=0;for(int i=1;i<=n;i++){if((a[i]&&!b[i])||!a[i]){t++;if(find(i)){tot++;}//else//break;}}if(tot==cnt){printf("^_^\n");}elseprintf("T_T\n");}return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的洛谷P2055 [ZJOI2009]假期的宿舍 题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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