ZOJ-1654 Place the Robots---二分图最小点覆盖+构图

题目链接：

https://vjudge.net/problem/ZOJ-1654

题目大意：

有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。

解题思路：

和POJ-2226类似

我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人，我们把这些块编上号。同样，把竖直方向的块也编上号。如下图：

把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二分图：

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<queue>
  7 using namespace std;
  8 typedef pair<int, int> Pair ;
  9 typedef long long ll;
 10 const int INF = 0x3f3f3f3f;
 11 const int maxn = 2500 + 10;
 12 vector<int>G[maxn];
 13 int cx[maxn], cy[maxn];
 14 int cntx, cnty;
 15 bool vis[maxn];
 16 
 17 void init(int n)
 18 {
 19     for(int i = 0; i <= n; i++)G[i].clear();
 20 }
 21 bool dfs(int u)
 22 {
 23     for(int i = 0; i < G[u].size(); i++)
 24     {
 25         int v = G[u][i];
 26         if(!vis[v])
 27         {
 28             vis[v] = 1;
 29             if(cy[v] == -1 || dfs(cy[v]))
 30             {
 31                 cx[u] = v;
 32                 cy[v] = u;
 33                 return true;
 34             }
 35         }
 36     }
 37     return false;
 38 }
 39 
 40 int maxmatch()
 41 {
 42     memset(cx, -1, sizeof(cx));
 43     memset(cy, -1, sizeof(cy));
 44     int ans = 0;
 45     for(int i = 1; i <= cntx; i++)
 46     {
 47         if(cx[i] == -1)
 48         {
 49             memset(vis, 0, sizeof(vis));
 50             ans += dfs(i);
 51         }
 52     }
 53     return ans;
 54 }
 55 char Map[55][55];
 56 int T, n, m, cases;
 57 void build_Map()
 58 {
 59     //横向标号
 60     int a[55][55], b[55][55];
 61     memset(a, 0, sizeof(a));
 62     memset(b, 0, sizeof(b));
 63     cntx = cnty = 0;
 64     for(int i = 0; i < n; i++)
 65     {
 66         for(int j = 0; j < m; j++)
 67         {
 68             if(Map[i][j] == 'o')
 69             {
 70                 a[i][j] = ++cntx;
 71                 j++;
 72                 while(j < m && Map[i][j] != '#')
 73                     a[i][j] = a[i][j - 1], j++;
 74             }
 75         }
 76     }
 77     //竖向编号
 78     for(int j = 0; j < m; j++)
 79     {
 80         for(int i = 0; i < n; i++)
 81         {
 82             if(Map[i][j] == 'o')
 83             {
 84                 b[i][j] = ++cnty;
 85                 i++;
 86                 while(i < n && Map[i][j] != '#')
 87                     b[i][j] = b[i - 1][j], i++;
 88             }
 89         }
 90     }
 91     init(cntx);//初始化Map
 92     for(int i = 0; i < n; i++)
 93         for(int j = 0; j < m; j++)
 94         if(Map[i][j] == 'o')G[a[i][j]].push_back(b[i][j]);
 95 }
 96 int main()
 97 {
 98 
 99     cin >> T;
100     while(T--)
101     {
102         cin >> n >> m;
103         for(int i = 0; i < n; i++)cin >> Map[i];
104         build_Map();
105         printf("Case :%d
", ++cases);
106         cout<<maxmatch()<<endl;
107     }
108     return 0;
109 }