洛谷p2055:假期宿舍(二分图)

题目描述
学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。
比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床。而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。
我们已知一共有 n 个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

题意很简单:显然一个人睡一张床是一个一对一的匹配关系，可以建二分图来跑最大匹配。将每个点分成两份，一份表示人，一份表示对应的床。如果A是在校学生并且不回家，那么A可以跟所有他认识的在校学生的床连线，并且可以跟自己连线，一个注意点就是 不能跟不在校的学生连线，因为他没床。 如果A 是在校学生并且回家了，那么直接continue,不需要连任何线（他又不睡学校），如果A 是 外校人，那么A可以跟所有他认识的在校学生的床连线。
图建好跑一个最大匹配，显然就是答案了。

#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
const int maxn = 1e3+10;
int t,n;
int a[maxn],b[maxn],mat[maxn][maxn];
int link[maxn][maxn],used[maxn],nxt[maxn];
bool find(int u){
 	for(int i = 1; i <= n; i++){
  		if(link[u][i] && !used[i]){
   			used[i] = 1;
   			if(!nxt[i] || find(nxt[i])){
    				nxt[i] = u;
    				return true;
   			}
  		}
 	}
 	return false;
}
bool match(int ans){
 	int res = 0;
 	for(int i = 1; i <= n; i++){
  		memset(used,0,sizeof(used));
  		if(find(i)) res++;
 	}
 	return res == ans;
}	
int main(){
 	cin >> t;
 	while(t--){
  		cin >> n;
  		int f,res = n;
  		memset(a,0,sizeof(a));
  		memset(b,0,sizeof(b));
  		memset(mat,0,sizeof(mat));
  		memset(link,0,sizeof(link));
  		memset(nxt,0,sizeof(nxt));
  		for(int i = 1; i <= n; i++)
   			cin >> a[i];
  		for(int i = 1; i <= n; i++){
   			cin >> b[i];
   			if(a[i] && b[i]) res--;
  		}
  		for(int i = 1; i <= n; i++)
   			for(int j = 1; j <= n; j++)
    				cin >> mat[i][j];
  		for(int i = 1; i <= n; i++){
   			if(a[i] && b[i]) continue;
   			if(a[i]) link[i][i] = 1;
   			for(int j = 1; j <= n; j++){
    				if(!a[j] || !mat[i][j]) continue;
    				link[i][j] = 1;
   			}
  		}
  		if(match(res)) cout << "^_^" << endl;
  		else cout << "T_T" << endl;
 }
}