P2055-[ZJOI2009]假期的宿舍

  1 #include <bits/stdc++.h>
  2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
  3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
  4 #define maxn 139*2
  5 #define INF 0x3f3f3f3f
  6 #define MOD 1000000007
  7 typedef long long ll;
  8 using namespace std;
  9 inline ll read()
 10 {
 11     ll ans = 0;
 12     char ch = getchar(), last = ‘ ‘;
 13     while(!isdigit(ch)) last = ch, ch = getchar();
 14     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar();
 15     if(last == ‘-‘) ans = -ans;
 16     return ans;
 17 }
 18 inline void write(ll x)
 19 {
 20     if(x < 0) x = -x, putchar(‘-‘);
 21     if(x >= 10) write(x / 10);
 22     putchar(x % 10 + ‘0‘);
 23 }
 24 int n;
 25 int isST[maxn],goHM[maxn];
 26 int beFM[maxn][maxn];
 27 int a[maxn][maxn];
 28 bool used[maxn];
 29 void get()
 30 {
 31     n = read();
 32     memset(isST,0,sizeof(isST));
 33     memset(goHM,0,sizeof(goHM));
 34     memset(beFM,0,sizeof(beFM));
 35     memset(a,0,sizeof(a));
 36     _for(i,0,n)
 37         isST[i] = read();
 38     _for(i,0,n)
 39     {
 40         int a = read();
 41         if(!isST[i])
 42             continue;
 43         goHM[i] = a;
 44     }
 45     _for(i,0,n)
 46     _for(j,0,n)
 47     beFM[i][j] = read();
 48 }
 49 int linker[maxn];
 50 int cnt = 0;
 51 bool dfs(int u)
 52 {
 53     _for(v,0,n)
 54         if(isST[v] && a[u][v] && !used[v])
 55         {
 56             used[v] = true;
 57             if(linker[v] == -1 || dfs(linker[v]))
 58             {
 59                 linker[v] = u;
 60                 return true;
 61             }
 62         }
 63     return false;
 64 }
 65 int hungry()
 66 {
 67     int res = 0;
 68     memset(linker,-1,sizeof(linker));
 69     _for(u,0,n)
 70     {
 71         memset(used,false,sizeof(used));
 72         if((!isST[u] || (isST[u]&&!goHM[u])) && dfs(u))
 73             res    ++;
 74     }
 75     return res;
 76 }
 77 int main()
 78 {
 79     int T;
 80     T = read();
 81     while(T--)
 82     {
 83         get();
 84         cnt = 0;
 85         _for(i,0,n)
 86         if(!isST[i] || (isST[i]&&!goHM[i]))
 87             cnt ++;
 88         _for(i,0,n)
 89         {
 90             if(isST[i] && !goHM[i])
 91                 a[i][i] = 1;
 92             _for(j,0,n)
 93             if(beFM[i][j] && isST[j])
 94                 a[i][j] = 1;
 95         }
 96         if(hungry()==cnt)
 97             printf("^_^\n");
 98         else
 99             printf("T_T\n");
100     }
101     return 0;
102 }