P2055

rq_hyj · 2025-01-10 17:07:19 · 个人记录

#include<cstdio>
#include<iostream>
using namespace std;
int len;
int n;
int sch[55],hom[55];
int mp[55][55];
int t[55],link[55];
int poi;
int fla;
void ddxyz(){
    fla=0;
    for(int i=1;i<=50;i++){
        link[i]=0;
        for(int j=1;j<=50;j++){
            mp[i][j]=0;
        }
    }
}
bool find(int xy){
    for(int i=1;i<=n;i++){
        if(sch[i]==1&&mp[xy][i]==1&&t[i]!=poi){//sch[i]==1判断这个人是否在校（是否有床位） 
            t[i]=poi;
            if(link[i]==0||find(link[i])){
                link[i]=xy;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    cin>>len;
    while(len--){
        ddxyz();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&sch[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&hom[i]);
            if(sch[i]==0&&hom[i]==0){
                hom[i]=1;
            } 
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&mp[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            if(sch[i]==1&&hom[i]==0){//判断他是否在校且不回家
                mp[i][i]=1;
            }
        }
        for(int i=1;i<=n;i++){
            if(sch[i]==1&&hom[i]==1){//判断若一个人既在校又回家就代表他的床位空出来了不需要进行调用 
                continue;
            }
            ++poi;
            if(find(i)==0){
                printf("T_T\n");
                fla=1;
                break;
            }
        }
        if(fla==0){
            printf("^_^\n");
        }
    }
    return 0;
}