\(\color{red}{Link}\)

\(\text{Solution:}\)

把人和床看成点，问题转化为二分图。

于是，对于每一个在校生，我们建立出他的床点；然后对于每一个在校生，他们自己可以和自己的床位连边。

对于其他人：每一个人都可以和他认识的人连边。当然，对于在校生不留下的人，可以省去连边。

于是，本题转化为网络流模型：源点向人连边，人向床连边，床向汇点连边，跑完最大流后判断其是不是等于所有需要床位的人的数量。等于则有解，不等则无解。

using namespace std;
const int MAXN=4000;
const int inf=2147483647;
int T,n,vis[1000],v[1000],S,TT;
int a[1000][1000],tot=1,head[MAXN];
struct edge{
    int nxt,to,flow;
}e[MAXN];
inline void add(int x,int y,int w){
    e[++tot].to=y;e[tot].nxt=head[x];
    e[tot].flow=w;head[x]=tot;
    e[++tot].to=x;e[tot].nxt=head[y];
    e[tot].flow=0;head[y]=tot;
}
int dep[MAXN],cur[MAXN];
bool bfs(int s,int t){
    memset(dep,0,sizeof(dep));
    queue<int>q;q.push(s);
    dep[s]=1;cur[s]=head[s];
    while(!q.empty()){
        s=q.front();q.pop();
        for(int i=head[s];i;i=e[i].nxt){
            int j=e[i].to;
            if(!dep[j]&&e[i].flow){
                dep[j]=dep[s]+1;
                cur[j]=head[j];
                if(j==t)return true;
                q.push(j);
            }
        }
    }
    return false;
}
int dfs(int s,int flow,int t){
    if(s==t||flow<=0)return flow;
    int rest=flow;
    for(int i=cur[s];i;i=e[i].nxt){
        int j=e[i].to;
        if(dep[j]==dep[s]+1&&e[i].flow){
            int tmp=dfs(j,min(rest,e[i].flow),t);
            if(tmp<=0)dep[j]=0;
            rest-=tmp;e[i].flow-=tmp;e[i^1].flow+=tmp;
            if(rest<=0)break;
        }
    }
    return flow-rest;
}
int dinic(int s,int t){
    int ans=0;
    for(;bfs(s,t);)ans+=dfs(s,inf,t);
    return ans;
}
void solve(){
    tot=1;int sum=0;
    for(int i=1;i<=n;++i){
        if(vis[i]&&v[i])continue;
        sum++;
    }
    for(int i=1;i<=n;++i){
        if(v[i]&&vis[i])continue;
        for(int j=1;j<=n;++j){
            if(a[i][j]&&vis[j])add(i,j+n,1);
        }
    }
    S=0,T=2*n+1;
    for(int i=1;i<=n;++i)if(vis[i]&&!v[i])add(i,i+n,1);
    for(int i=1;i<=n;++i){add(S,i,1);}
    for(int i=1;i<=n;++i)if(vis[i])add(i+n,T,1);
    int Sum=dinic(S,T);
    if(Sum==sum)puts("^_^");
    else puts("T_T");
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            a[i][j]=0;
    for(int i=0;i<=n+n;++i)head[i]=dep[i]=cur[i]=vis[i]=v[i]=0;
    for(int i=1;i<=tot;++i)e[i].flow=e[i].nxt=e[i].to=0;
}
int main(){
    scanf("%d",&TT);
    while(TT--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)scanf("%d",&vis[i]);
        for(int i=1;i<=n;++i)scanf("%d",&v[i]);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                scanf("%d",&a[i][j]);
        solve();
    }
    return 0;
}