4185 Oil Skimming 最大匹配 奇偶建图

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<vector>
  6 #include<algorithm>
  7 using namespace std;
  8 const int N=36005,INF=0x3f3f3f3f;
  9 int cx[N],cy[N],dx[N],dy[N];
 10 bool bmask[N];
 11 vector<int > bmap[N];
 12 int nx,ny,dis,ans;
 13 bool searchpath()
 14 {
 15     queue<int> q;
 16     dis=INF;
 17     memset(dx,-1,sizeof(dx));
 18     memset(dy,-1,sizeof(dy));
 19     for(int i=1;i<=nx;i++)
 20     {
 21         if(cx[i]==-1){ q.push(i); dx[i]=0; }
 22         while(!q.empty())
 23         {
 24             int u=q.front(); q.pop();
 25             if(dx[u]>dis) break;
 26             for(int i=0;i<bmap[u].size();i++)
 27             {
 28                 int v=bmap[u][i];
 29                 if(dy[v]==-1)
 30                 {
 31                     dy[v]= dx[u] + 1;
 32                     if(cy[v]==-1) dis=dy[v];
 33                     else
 34                     {
 35                         dx[cy[v]]= dy[v]+1;
 36                         q.push(cy[v]);
 37                     }
 38                 }
 39             }
 40         }
 41     }
 42     return dis!=INF;
 43 }
 44 int findpath(int u)
 45 {
 46     for(int i=0;i<bmap[u].size();i++)
 47     {
 48         int v=bmap[u][i];
 49         if(!bmask[v]&&dy[v]==dx[u]+1)
 50         {
 51             bmask[v]=1;
 52             if(cy[v]!=-1&&dy[v]==dis) continue;
 53             if(cy[v]==-1||findpath(cy[v]))
 54             {
 55                 cy[v]=u; cx[u]=v;
 56                 return 1;
 57             }
 58         }
 59     }
 60     return 0;
 61 }
 62 void maxmatch()
 63 {
 64     ans=0;
 65     memset(cx,-1,sizeof(cx));
 66     memset(cy,-1,sizeof(cy));
 67     while(searchpath())
 68     {
 69         memset(bmask,0,sizeof(bmask));
 70         for(int i=1;i<=nx;i++)
 71             if(cx[i]==-1) ans+=findpath(i);
 72     }
 73 }
 74 void init()
 75 {
 76     for(int i=0;i<=N;i++) bmap[i].clear();
 77 }
 78 char s[605][605];
 79 int Map[605][605];
 80 int main()
 81 {
 82     //freopen("test.txt","r",stdin);
 83     int cas,n,i,j,k=1,a,b,t=1;
 84     char ch;
 85     scanf("%d",&cas);
 86     while(cas--)
 87     {
 88         scanf("%d",&n);
 89         t=0;
 90         for(i=1;i<=n;i++){
 91             getchar();
 92             for(j=1;j<=n;j++)
 93             {
 94                 scanf("%c",&s[i][j]);
 95                 if(s[i][j]==‘#‘) Map[i][j]=++t;
 96             }
 97         }
 98         init();
 99         for(i=1;i<=n;i++)
100         {
101             for(j=1;j<=n;j++)
102             {
103                 if(s[i][j]==‘#‘&&((i+j)%2))
104                 {
105                     a=Map[i][j];
106                     if(i>1&&s[i-1][j]==‘#‘){
107                         b=Map[i-1][j];
108                         bmap[a].push_back(b);
109                     }
110                     if(i<n&&s[i+1][j]==‘#‘){
111                         b=Map[i+1][j];
112                         bmap[a].push_back(b);
113                     }
114                     if(j>1&&s[i][j-1]==‘#‘){
115                         b=Map[i][j-1];
116                         bmap[a].push_back(b);
117                     }
118                     if(j<n&&s[i][j+1]==‘#‘){
119                         b=Map[i][j+1];
120                         bmap[a].push_back(b);
121                     }
122                 }
123             }
124         }
125         nx=t;
126         maxmatch();
127         printf("Case %d: %d\n",k++,ans);
128     }
129     return 0;
130 }