【BZOJ 1433】[ZJOI2009] 假期的宿舍

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1433

真·水题

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const int M = 100000;
const int INF = 100000000;

int head[N],nxt[M],to[M],flow[M],TT,in_school[N],live_school[N];
int n,vout,dis[N],cur[N],S,T; queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v, int f) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    dis[S] = 0; que.push(S);
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    } return ~dis[T];
}
 
int DFS(int w, int f) {
    if (w == T) return f;
    else { int ret = 0;
        for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
            int tmp = DFS(to[i], min(f, flow[i]));
            ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
            if (!f) break;
        } return ret;
    }
}
 
inline int Dinic(){
    int ret = 0; while (BFS()) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(S,INF);
    } return ret;
}

int main(){
	int TTT; cin>>TTT; while (TTT--) {
		memset(head,0,sizeof(head));
		memset(in_school,0,sizeof(in_school));
		memset(live_school,0,sizeof(live_school));
		n = read(); vout = 0; TT = 1; S = 0; T = N-1; 
		for (int i=1;i<=n;i++) if (read()) Add_Edge(i+n,T,1), live_school[i] = 1;
		for (int i=1;i<=n;i++) if (!read()) Add_Edge(i,i+n,1), in_school[i] = 1;
		for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) if (read()) Add_Edge(i,j+n,1);
		for (int i=1;i<=n;i++) if (in_school[i] || !live_school[i]) Add_Edge(S,i,1), vout++;
		if(Dinic() == vout)puts("^_^");
        else puts("T_T");
	}
	return 0;
}