BZOJ 1433 假期的宿舍 二分图匹配

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<vector>
  4 #include<queue>
  5 #include<cstring>
  6 #define rep(i,j,k) for(int i = j; i <= k; i++)
  7 #define maxn 60
  8 #define clr(i,j) memset(i,j,sizeof(i))
  9 using namespace std;
 10  
 11 vector<int> g[maxn];
 12 int mx[maxn], my[maxn], dx[maxn], dy[maxn], n1;
 13 queue<int> q;
 14 bool vis[maxn];
 15  
 16 bool match(int now)
 17 {
 18     int s = g[now].size();
 19     rep(i,0,s-1){
 20         int to = g[now][i];
 21         if( !vis[to] && dy[to] == dx[now] + 1 ){
 22             vis[to] = 1;
 23             if( !my[to] || match(my[to]) ){
 24                 my[to] = now, mx[now] = to;
 25                 return 1;
 26             }
 27         }
 28     }
 29     return 0;
 30 }
 31  
 32 int erfen()
 33 {
 34     clr(mx,0); clr(my,0); int ans = 0;
 35     while( 1 ){
 36         clr(dx,0), clr(dy,0);
 37         while( !q.empty() ) q.pop();
 38         rep(i,1,n1){
 39             if( !mx[i] ) q.push(i);
 40         }
 41         bool flag = 1;
 42         while( !q.empty() ){
 43             int now = q.front(); q.pop();
 44             int s = g[now].size();
 45             rep(i,0,s-1){
 46                 int to = g[now][i];
 47                 if( !dy[to] ){
 48                     dy[to] = dx[now] + 1;
 49                     if( my[to] ){
 50                         dx[my[to]] = dy[to] + 1;
 51                         q.push(my[to]);
 52                     }
 53                     else flag = 0;
 54                 }
 55             }
 56         }
 57         if( flag ) break;
 58         clr(vis,0);
 59         rep(i,1,n1){
 60             if( !mx[i] && match(i) ) ans++;
 61         }
 62     }
 63     return ans;
 64 }
 65  
 66 void clear()
 67 {
 68     rep(i,1,maxn) g[i].clear();
 69 }
 70  
 71 int read()
 72 {
 73     int s = 0,t = 1; char c = getchar();
 74     while( !isdigit(c) ){
 75         if( c == ‘-‘ ) t = -1; c = getchar(); 
 76     }
 77     while( isdigit(c) ){
 78         s = s * 10 + c- ‘0‘; c = getchar();
 79     }
 80     return s * t;
 81 }
 82  
 83 bool bed[maxn], home[maxn];
 84 bool used[maxn][maxn];
 85  
 86 int main()
 87 {
 88     int t = read();
 89     while( t-- ){
 90         clear();
 91         clr(used,0);  clr(bed,0); clr(home,0);
 92         int n = read();
 93         n1 = n;
 94         rep(i,1,n){
 95             bed[i] = read();
 96         }
 97         int tot = 0;
 98         rep(i,1,n) {
 99             int x = read();
100             if( bed[i] && x == 1 ) {
101                 home[i] = 1;  
102                 tot++;
103             }
104         }
105         rep(i,1,n){
106             rep(j,1,n){
107                 int x = read();
108                 if( i == j && bed[i] && !home[i] && !used[i][i] ) {
109                      g[i].push_back(i);
110                      used[i][i] = 1;
111                 }
112                 else if( i != j && x ){
113                     if( bed[i] && !home[j] && !used[j][i] ) {
114                         g[j].push_back(i);
115                         used[j][i] = 1;
116                     }
117                     if( bed[j] && !home[i] && !used[i][j]) {
118                         used[i][j] = 1;
119                         g[i].push_back(j);
120                     }
121                 }
122             }
123         }
124         if( erfen() == n - tot ) printf("%c%c%c\n", 94,95,94);
125         else printf("%c%c%c\n", 84,95,84);
126     }
127     
128     return 0;
129 }