P2055-[ZJOI2009]假期的宿舍

左手的ㄟ右手 2023-06-01 08:55 78阅读 0赞

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 }

转载于:https://www.cnblogs.com/Asurudo/p/11544198.html