题目大意：一个住校的问题，给出那些人住校，那些人不住校，那些人和那些人认识，认识的人可以谁他的床，问能不能满足所有人都有床住。
思路：二分图最大匹配，当然也可以用网络流来做。建图方法如下：
1.住校的人向T连边
2.想睡的人从S连边
3.互相认识的人连边
然后跑最大流，判断是否满流，输出结果。
CODE：
#include
#include
#include
#include
#include
#define MAX 110 #define S 0 #define T (points << 1|1) #define INF 0x3f3f3f3f using namespace std; int cases,points; int map[MAX][MAX]; int have_bed[MAX]; int deep[MAX]; bool BFS(); int Dinic(int x,int flow); int main() { for(cin >> cases;cases; --cases) { scanf("%d",&points); int cnt = 0; memset(map,0,sizeof(map)); for(int i = 1;i <= points; ++i) { scanf("%d",&have_bed[i]); if(have_bed[i]) map[i + points][T] = 1; } for(int x,i = 1;i <= points; ++i) { scanf("%d",&x); if(!have_bed[i] || (have_bed[i] && !x)) map[S][i] = 1,cnt++; } for(int i = 1;i <= points; ++i) for(int x,j = 1;j <= points; ++j) { scanf("%d",&x); if(x || i == j) map[i][j + points] = 1; } int ans = 0; while(BFS()) ans += Dinic(S,INF); if(ans == cnt) puts("^_^"); else puts("T_T"); } return 0; } bool BFS() { static queue
q; while(!q.empty()) q.pop(); memset(deep,0,sizeof(deep)); deep[S] = 1; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = S;i <= T; ++i) if(map[x][i] && !deep[i]) { deep[i] = deep[x] + 1; q.push(i); if(i == T) return true; } } return false; } int Dinic(int x,int flow) { if(x == T) return flow; int temp = flow; for(int i = S;i <= T; ++i) if(deep[i] == deep[x] + 1 && map[x][i] && temp) { int away = Dinic(i,min(temp,map[x][i])); if(!away) deep[i] = 0; map[x][i] -= away; map[i][x] += away; temp -= away; } return flow - temp; }