solution-code3950

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define inf 0x3F3F3F3F
6
using namespace std;
7
struct Node
8
{
9
  int to,next,v;
10
}e[100005];
11
int S,T,P,a[1005],b[1005],h[1005],d[1005],gap[1005],cnt=1;
12
inline void Addedge(int x,int y,int v)
13
{
14
  e[++cnt]=(Node){y,h[x],v};h[x]=cnt;
15
  e[++cnt]=(Node){x,h[y],0};h[y]=cnt;
16
  return;
17
}
18
inline int dfs(int x,int maxf)
19
{
20
  if(x==T)return maxf;
21
  int i,y,ret=0,delta;
22
  for(i=h[x];i;i=e[i].next)
23
  {
24
    y=e[i].to;
25
    if(e[i].v&&d[x]==d[y]+1)
26
    {
27
      delta=dfs(y,min(maxf,e[i].v));
28
      e[i].v-=delta;
29
      e[i^1].v+=delta;
30
      ret+=delta;
31
      maxf-=delta;
32
      if(d[S]==P||!maxf)return ret;
33
    }
34
  }
35
  if(!(--gap[d[x]]))d[S]=P;
36
  ++gap[++d[x]];
37
  return ret;
38
}
39
inline int SAP()
40
{
41
  int sum=0;
42
  gap[0]=P;
43
  while(d[S]<P)sum+=dfs(S,inf);
44
  return sum;
45
}
46
int main(void)
47
{
48
  int i,j,x,n,Case,sum=0;
49
  scanf("%d",&Case);
50
  while(Case--)
51
  {
52
    memset(d,0,sizeof(d));
53
    memset(gap,0,sizeof(gap));
54
    memset(h,0,sizeof(h));cnt=1;sum=0;
55
    scanf("%d",&n);
56
    S=n*2+1;P=T=n*2+2;
57
    for(i=1;i<=n;++i)scanf("%d",&a[i]);
58
    for(i=1;i<=n;++i)scanf("%d",&b[i]);
59
    for(i=1;i<=n;++i)
60
    {
61
      for(j=1;j<=n;++j)
62
      {
63
        scanf("%d",&x);
64
        if(x)Addedge(i,j+n,1);
65
      }
66
    }
67
    for(i=1;i<=n;++i)
68
    {
69
      if(a[i]&&b[i])continue;
70
      Addedge(S,i,1);++sum;
71
    }
72
    for(i=1;i<=n;++i)
73
    {
74
      if(!a[i])continue;
75
      Addedge(i,i+n,1);
76
      Addedge(i+n,T,1);
77
    }
78
    if(SAP()==sum)printf("^_^\n");
79
    else printf("T_T\n");
80
  }
81
  return 0;
82
}