题目

 

Description

 

学校放假了······有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如A 和B都是学校的学生，A要回家，而C来看B，C与A不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一 个解决方案就是B睡A的床而C睡B的床。而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也 不一定都互相认识。我们已知一共有n个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家 。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。  

 

Input

 

第一行一个数T表示数据组数。接下来T组数据， 每组数据第一行一个数n表示涉及到的总人数。 接下来一行n个数，第i个数表示第i个人是否是在校学生(0表示不是，1表示是)。 再接下来一行n个数，第i个数表示第i个人是否回家 (0表示不回家，1表示回家，注意如果第i个人不是在校学生，那么这个位置上的数是一个随机的数， 你应该在读入以后忽略它)。 接下来n行每行n个数， 第i行第j个数表示i和j是否认识 (1表示认识，0表示不认识，第i行i个的值为0，但是显然自己还是可以睡自己的床)， 认识的关系是相互的。 1 ≤ n ≤ 50,1 ≤ T ≤ 20  

 

Output

 

对于每组数据，如果存在一个方案则输出“^_^”(不含引号)否则输出“T_T”(不含引号)。 (注意输出的都是半角字符，即三个符号的ASCII码分别为94,84,95)

 

Sample Input

 

1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

 

 

分析

• 网络流

• 想想如何构图简单？？
• 好的，我们将所有在校的床位与原点 0 连接
• 将所有需要床位的与汇点 100 连接
• 然后我们要连接中间的线
• 我们可以这么做：
• 因为存在在校学生不回家，所以我们就将 i 和 i+n 相连接
• 然后就是外校学生与可以睡的人连接  i 和 j+n 连接
• 跑一个最大流
• 如果最大流==我的需要床位数 en

 

代码

  1 #include<iostream>
  2 #include<cstring>
  3 #include<queue>
  4 using namespace std;
  5 
  6 const int maxn=1e5+10;
  7 const int maxe=4e5+10;
  8 const int inf=0x3f3f3f3f;
  9 
 10 queue <int> q;
 11 int dis[maxn],n,s,t,ls[maxn],a[maxn],cnt;
 12 struct edge
 13 {
 14     int to,c,op,next;
 15 }e[maxe];
 16 
 17 void add(int x,int y,int w)
 18 {
 19     e[++cnt]=(edge){y,w,cnt+1,ls[x]};
 20     ls[x]=cnt;
 21     e[++cnt]=(edge){x,0,cnt-1,ls[y]};
 22     ls[y]=cnt;
 23 }
 24 
 25 bool bfs()
 26 {
 27     memset(dis,inf,sizeof(dis));
 28     while (!q.empty()) q.pop();
 29     q.push(s);
 30     dis[s]=0;
 31     while (!q.empty())
 32     {
 33         int x=q.front(); q.pop();
 34         for (int i=ls[x];i;i=e[i].next)
 35         {
 36             int y=e[i].to;
 37             if (e[i].c&&dis[y]>dis[x]+1)
 38             {
 39                 dis[y]=dis[x]+1;
 40                 if (y==t) return 1;
 41                 q.push(y);
 42             }
 43         }
 44     }
 45     return 0;
 46 }
 47 
 48 int dfs(int x,int maxf)
 49 {
 50     if (x==t) return maxf;
 51     int ret=0;
 52     for (int i=ls[x];i;i=e[i].next)
 53     {
 54         int y=e[i].to;
 55         if (e[i].c&&dis[y]==dis[x]+1)
 56         {
 57             int f=dfs(y,min(e[i].c,maxf-ret));
 58             if (!f) dis[y]=-1;
 59             e[i].c-=f;
 60             e[e[i].op].c+=f;
 61             ret+=f;
 62             if (ret==maxf) break;
 63         }
 64     }
 65     return ret;
 66 }
 67 
 68 int dinic()
 69 {
 70     int flow=0;
 71     while (bfs())
 72         flow+=dfs(s,inf);
 73     return flow;
 74 }
 75 
 76 int main ()
 77 {
 78      int T;
 79      cin>>T;
 80      while (T--)
 81      {
 82          memset(e,0,sizeof(e));
 83          memset(ls,0,sizeof(ls));
 84          int tot=0,ans=0;
 85          cnt=0;
 86          cin>>n;
 87          s=0;
 88          t=101;
 89          for (int i=1;i<=n;i++)
 90          {
 91              cin>>a[i];
 92              if (a[i]) add(0,i,1);
 93          }
 94          int x;
 95          for (int i=1;i<=n;i++)
 96          {
 97              cin>>x;
 98              if ((a[i]&&!x)||!a[i]) 
 99              {
100                  add(i+n,t,1);
101                  tot++;
102              }
103          }
104          for (int i=1;i<=n;i++)
105          {
106              for (int j=1;j<=n;j++)
107              {
108                  cin>>x;
109                  if (x||i==j) add(i,j+n,1);
110              }
111          }
112          if (dinic()==tot) cout<<"^_^"<<endl;
113          else cout<<"T_T"<<endl;
114      }
115 }