建图是件难事233.
#include#include #include #include #include using namespace std;struct node{ int point; int value; int nxt;};node line[500000];int head[5000],tail=-1;void add(int x,int y,int z){ line[++tail].point=y; line[tail].value=z; line[tail].nxt=head[x]; head[x]=tail; line[++tail].point=x; line[tail].value=0; line[tail].nxt=head[y]; head[y]=tail;}int n;int stu[1000];int back[1000];int dep[1000];int cur[1000];bool bfs(int begin,int end){ memset(dep,0,sizeof(dep)); queue q; q.push(begin); dep[begin]=1; for(int i=0;i<=2*n+1;i++) cur[i]=head[i]; while(!q.empty()) { int pas=q.front(); q.pop(); for(int i=head[pas];i!=-1;i=line[i].nxt) { if(!dep[line[i].point]&&line[i].value) { dep[line[i].point]=dep[pas]+1; q.push(line[i].point); } } } if(!dep[end]) return false; return true;}int dfs(int now,int aim,int limte){ if(now==aim||!limte) return limte; int flow=0,f; for(int i=cur[now];i!=-1;i=line[i].nxt) { cur[now]=i; if(dep[line[i].point]==dep[now]+1&&(f=dfs(line[i].point,aim,min(limte,line[i].value)))) { limte-=f; flow+=f; line[i].value-=f; line[i^1].value+=f; if(!limte) break; } } return flow;}int dinic(int begin,int end){ int res=0; while(bfs(begin,end)) res+=dfs(begin,end,0x7fffffff); return res;}int main(){ int t; scanf("%d",&t); while(t--) { int tot=0; tail=-1; memset(stu,0,sizeof(stu)); memset(back,0,sizeof(back)); scanf("%d",&n); for(int i=0;i<=2*n+1;i++) head[i]=-1; for(int i=1;i<=n;i++) { scanf("%d",&stu[i]); if(stu[i]) add(i+n,2*n+1,1); } for(int i=1;i<=n;i++) { scanf("%d",&back[i]); if(!stu[i]||(stu[i]&&!back[i])) { add(0,i,1); tot+=1; } } int a; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&a); if(a||i==j) add(i,j+n,1); } int ans=dinic(0,2*n+1); if(ans>=tot) printf("^_^\n"); else printf("T_T\n"); } }