P2055 [ZJOI2009] 假期的宿舍

P2055 [ZJOI2009] 假期的宿舍

大意

要求满足不回家的人和外校的人都有床睡，一个人只会睡自己认识的人的床。

思路

考虑二分图最大匹配。

然后，这个点 \(u \to v\) 连边的前置条件是 \(v\) 是在校学生，且 \(v\) 回家睡觉。

需要注意的是，自己显然是可以睡自己的床的（并非废话），只要这个学生在校且不回家，就可以 \(u \to u\)。

将图建出来之后，直接跑二分图最大匹配即可。

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;const int MAXN = 55;
int n;
int T;
bool at[MAXN];
int home[MAXN];
vector<int> g[MAXN];
int mac[MAXN];
bool vis[MAXN];bool dfs(int u){for(int &v : g[u]){if(!vis[v]){vis[v] = 1;if(mac[v] == -1 || dfs(mac[v])){mac[v] = u;return true;}}}return false;
}int hungary(int n){int cnt = 0;memset(mac, -1, sizeof(mac));for(int i = 1;i <= n;i ++){memset(vis, 0, sizeof(vis));if(!at[i] || (at[i] && !home[i])) cnt += dfs(i);}return cnt;
}int main(){cin >> T;while(T --){int sum = 0;cin >> n;for(int i = 1;i <= n;i ++) g[i].clear();for(int i = 1;i <= n;i ++){cin >> at[i];}for(int i = 1;i <= n;i ++){cin >> home[i];if(!home[i] && at[i]){g[i].push_back(i);}}for(int i = 1;i <= n;i ++){if(!at[i] || (at[i] && !home[i])) sum ++;}for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++){bool rela; cin >> rela;if(rela && at[j]){g[i].push_back(j);}}}if(hungary(n) == sum){cout << "^_^\n";}else{cout << "T_T\n";}}return 0;
}