黑白棋

黑白棋

题目链接：http://acm.xidian.edu.cn/problem.php?id=1045

二分图匹配

乍看什么思路都没有，后来才知道是二分图问题：因为对手只能选相邻的块，如果整个联通快形成了一个完美匹配的二分图，那么无论先手怎么下，后手总可以找到相邻的块。所以，题目就转换为了寻找不完美匹配的二分图（简直了）。

和游少讨论了一会才明白注释那里的意思，然后我发现这次写的struct G可以当做模板了233333

代码如下：

  1 #include<cstdio>
  2 #include<vector>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 #define met(a,b) memset(a,b,sizeof(a))
  7 #define N 5
  8 using namespace std;
  9 typedef pair<int,int> P;
 10 int mp[N][N];
 11 int T;
 12 bool v[N*N];
 13 int sum;
 14 int dx[]={0,0,-1,1};
 15 int dy[]={-1,1,0,0};
 16 bool flag;
 17 struct G{
 18     vector<int>e[N*N];
 19     int match[N*N];
 20     bool vis[N*N];
 21     void init(){
 22         for(int i=0;i<N*N;++i)e[i].clear();
 23         met(match,-1);
 24     }
 25     void add(int from,int to){
 26         e[from].push_back(to);
 27         e[to].push_back(from);
 28     }
 29     bool dfs(int c){
 30         vis[c]=1;
 31         for(int i=0;i<e[c].size();++i){
 32             int w=e[c][i];
 33             int u=match[w];
 34             if(u<0||(!vis[u]&&dfs(u))){//!vis[u]:本次dfs(c)各个点只能重新匹配一次
 35                 match[c]=w;
 36                 match[w]=c;
 37                 return 1;
 38             }
 39         }
 40         return 0;
 41     }
 42     bool maxmatch(){
 43         int flow=0;
 44         for(int i=0;i<N*N;++i)
 45         if(v[i]&&match[i]==-1){
 46             met(vis,0);
 47             if(dfs(i))flow++;
 48         }
 49         if(sum==flow*2)return 0;
 50         else return 1;
 51     }
 52 };
 53 void init(){
 54     met(v,0);
 55     sum=0;
 56 }
 57 void bfs(int px,int py){
 58     G g;
 59     g.init();
 60     queue<P>q;
 61     mp[px][py]=1;
 62     q.push(make_pair(px,py));
 63     while(!q.empty()){
 64         P t=q.front();q.pop();
 65         v[t.first*N+t.second]=1;
 66         sum++;
 67         for(int i=0;i<4;++i){
 68             int x=t.first+dx[i];
 69             int y=t.second+dy[i];
 70             if(0<=x&&x<N&&0<=y&&y<N)
 71             if(mp[x][y]!=1){
 72                 mp[x][y]=1;
 73                 q.push(make_pair(x,y));
 74                 g.add(t.first*N+t.second,x*N+y);
 75             }
 76         }
 77     }
 78     flag=g.maxmatch();
 79 }
 80 
 81 int main(void){
 82     cin>>T;
 83     while(T--){
 84         flag=0;
 85         int i,j;
 86         for(i=0;i<N;++i)
 87         for(j=0;j<N;++j){
 88             char s;
 89             cin>>s;
 90             mp[i][j]=(s=='1'?1:0);
 91         }
 92         for(i=0;i<N;++i){
 93             for(j=0;j<N;++j)
 94             if(mp[i][j]!=1){
 95                 init();
 96                 bfs(i,j);
 97                 if(flag)break;
 98             }
 99             if(j!=N)break;
100         }
101         if(flag)cout<<"win"<<endl;
102         else cout<<"lose"<<endl;
103     }
104 }