```
#include<bits/stdc++.h>
using namespace std;
const int N=150,inf=1e9+10;
int T,n;
int c[N];
struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int w,int f) : from(u), to(v), cap(w), flow(f) {}
};
vector<int> G[N];
vector<Edge> edge;
int dep[N],cur[N],k;
void add(int u,int v,int w)
{
edge.push_back(Edge(u,v,w,0));
edge.push_back(Edge(v,u,0,0));
k=edge.size();
G[u].push_back(k-2);
G[v].push_back(k-1);
}
void init()
{
for(int i=1;i<=N;++i)
{
G[i].clear();
}
edge.clear();
}
bool vis[N];
bool bfs(int t)
{
memset(vis,0,sizeof(vis));
memset(dep,-1,sizeof(dep));
queue<int> q;
vis[0]=1;
dep[0]=0;
q.push(0);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<G[x].size();++i)
{
Edge& e=edge[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=1;
dep[e.to]=dep[x]+1;
q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int a,int t)
{
if(x==t||a==0)
{
return a;
}
int flow=0,f;
for(int& i=cur[x];i<G[x].size();++i)
{
Edge& e=edge[G[x][i]];
if(dep[e.to]==dep[x]+1&&(f=dfs(e.to,min(a,e.cap-e.flow),t)))
{
e.flow+=f;
edge[G[x][i]^1].flow-=f;
a-=f;
flow+=f;
if(a==0)
{
break;
}
}
}
return flow;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
init();
int ans=0;
for(int i=1;i<=n;++i)
{
int z;
scanf("%d",&z);
if(z)
{
add(i+n,2*n+1,1);
}
c[i]=z;
}
for(int i=1;i<=n;++i)
{
int a;
scanf("%d",&a);
if(!c[i]||(c[i]&&!a))
{
add(0,i,1);
++ans;
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
int w;
scanf("%d",&w);
if(w||i==j)
{
add(i,j+n,1);
}
}
}
int flow=0;
while(bfs(2*n+1))
{
memset(cur,0,sizeof(cur));
flow+=dfs(0,inf,2*n+1);
//cout<<flow<<endl;
}
if(flow==ans)
{
cout<<"^_^"<<endl;
}
else
{
cout<<"T_T"<<endl;
}
}
return 0;
}
```
新的
by Amon_Xolotl @ 2023-08-14 11:25:39