1433: [ZJOI2009]假期的宿舍
分析：
直接网络流，看是否满足即可。
S向每个有需要的人连边，有床的向T连边，认识的人之间互相连边。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = , INF = 1e9;
struct Edge { int to, nxt, cap; } e[];
int head[N], dis[N], cur[N], q[N], a[N];
int S, T, En; inline void add_edge(int u,int v,int w) {
++En; e[En].to = v, e[En].cap = w, e[En].nxt = head[u]; head[u] = En;
++En; e[En].to = u, e[En].cap = , e[En].nxt = head[v]; head[v] = En;
}
bool bfs() {
for (int i = ; i <= T; ++i) cur[i] = head[i], dis[i] = -;
int L = , R = ;
q[++R] = S; dis[S] = ;
while (L <= R) {
int u = q[L ++];
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] == - && e[i].cap > ) {
dis[v] = dis[u] + ;
q[++R] = v;
if (v == T) return true;
}
}
}
return false;
}
int dfs(int u,int flow) {
if (u == T) return flow;
int used = ;
for (int &i = cur[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] == dis[u] + && e[i].cap > ) {
int tmp = dfs(v, min(flow - used, e[i].cap));
if (tmp > ) {
used += tmp, e[i].cap -= tmp, e[i ^ ].cap += tmp;
if (used == flow) break;
}
}
}
if (used != flow) dis[u] = -;
return used;
}
int dinic() {
int ans = ;
while (bfs()) ans += dfs(S, INF);
return ans;
}
void solve() {
En = ;memset(head, , sizeof(head));
int n = read(), tot = ;
S = , T = n + n + ;
for (int i = ; i <= n; ++i) {
a[i] = read();
if (a[i]) add_edge(i + n, T, );
}
for (int i = ; i <= n; ++i) {
int x = read();
if ((a[i] && !x) || !a[i]) add_edge(S, i, ), tot ++;
}
for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j) {
int x = read();
if (x || i == j) add_edge(i, j + n, );
}
if (dinic() == tot) puts("^_^");
else puts("T_T");
}
int main() {
for (int Case = read(); Case --; solve());
return ;
}