记录编号	438635	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2009] 假期的宿舍	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2017-08-16 20:24:37	内存使用	0.56 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

#define MAXN (110)
#define INF (0x7fffffff)

struct EDGE{ 
    int to, cap;
    int ne;
    EDGE(int t, int n, int c) { 
        to = t, ne = n, cap = c;
    }
};

inline void add_edge(int fr, int to, int cap);
inline bool bfs(void);
int dfs(int u, int Min);

int head[MAXN];
bool is_student[MAXN], if_gohome[MAXN];
vector<EDGE> edge;
int TT, N, cnt;
int S, T, max_flow;
unsigned int bfn[MAXN];

int main() { 
#ifndef LOCAL
    freopen("zjoi09holiday.in", "r", stdin);
    freopen("zjoi09holiday.out", "w", stdout);
#endif
    TT = read();
    for(int t = 0; t < TT; ++t) { 
        memset(head, 0xff, sizeof(head));
        max_flow = cnt = 0;
        edge.clear();
        T = (N = read()) << 1 | 1;
        for(int i = 1; i <= N; ++i) { 
            is_student[i] = read();
            if(is_student[i]) add_edge(i + N, T, 1);
        }
        for(int i = 1; i <= N; ++i) { 
            if_gohome[i] = read();
            if(!is_student[i]) if_gohome[i] = false;
            if(!if_gohome[i]) add_edge(S, i, 1), ++cnt;
        }
        for(int i = 1; i <= N; ++i) 
            for(int j = 1; j <= N; ++j) { 
                if(read()) add_edge(i, j + N, 1);
                else if(i == j && is_student[i]) add_edge(i, i + N, 1);
            }
        while(bfs()) 
            max_flow += dfs(S, INF);
        if(cnt == max_flow) printf("^_^\n");
        else printf("T_T\n");
    }
    return 0;
}

inline void add_edge(int fr, int to, int cap) { 
    edge.push_back(EDGE(to, head[fr], cap)), head[fr] = edge.size() - 1;
    edge.push_back(EDGE(fr, head[to], 0)), head[to] = edge.size() - 1;
    return ;
}

inline bool bfs(void) { 
    static int u, v;
    queue<int> que;

    memset(bfn, 0x00, sizeof(bfn));
    que.push(S), bfn[S] = 1;

    while(!que.empty()) { 
        u = que.front();
        que.pop();
        if(u == T) return true;
        for(register int e = head[u]; ~e; e = edge[e].ne) { 
            if(bfn[v = edge[e].to] || !edge[e].cap) continue;
            bfn[v] = bfn[u] + 1;
            que.push(v);
        }
    }

    return false;
}

int dfs(int u, int Min) { 
    if(u == T) return Min;
    register int v, duolu = Min, tmp;
    for(register int e = head[u]; ~e; e = edge[e].ne) { 
        if(bfn[v = edge[e].to] == bfn[u] + 1 && edge[e].cap && (tmp = dfs(v, min(duolu, edge[e].cap)))) { 
            duolu -= tmp;
            edge[e].cap -= tmp;
            edge[e ^ 1].cap += tmp;
            if(!duolu) break;
        }
    }
    return Min - duolu;
}