UVa 12549 机器人警卫（最小点覆盖）

题意：

在一个Y行X列的网格里有空地（.），重要位置（*）和障碍物（#），用最少的机器人看守所有重要位置，每个机器人要放在一个格子里，面朝上下左右4个方向之一。机器人会发出激光，一直射到障碍物为止，沿途都是看守范围。

思路：

把每个坐标的x和y值连成一条边，分别作为二分图的两边，用最少的点去覆盖所有的边，也就是二分图的最大匹配。由于有障碍物的存在，在建图的时候需要拆分点。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<string>
  4 #include<cstring>
  5 using namespace std;
  6 
  7 const int maxn = 100 + 5;
  8 
  9 int n, m;
 10 int row_num, col_num;
 11 int map[maxn][maxn];
 12 int G[maxn][maxn];
 13 int match[maxn];
 14 int vis[maxn];
 15 
 16 pair<int, int> g[maxn][maxn];
 17 
 18 
 19 bool dfs(int u)
 20 {
 21     for (int j = 1; j <= col_num; j++)
 22     {
 23         if (!vis[j] && G[u][j])
 24         {
 25             vis[j] = 1;
 26             if (match[j] == -1 || dfs(match[j]))
 27             {
 28                 match[j] = u;
 29                 return true;
 30             }
 31         }
 32     }
 33     return false;
 34 }
 35 
 36 
 37 int main()
 38 {
 39     //freopen("D:\txt.txt", "r", stdin);
 40     int T;
 41     scanf("%d", &T);
 42     while (T--)
 43     {
 44         scanf("%d%d", &n, &m);
 45         memset(map, 0, sizeof(map));
 46         memset(G, 0, sizeof(G));
 47         memset(match, -1, sizeof(match));
 48         int t, x, y;
 49         scanf("%d", &t);
 50         while (t--)
 51         {
 52             scanf("%d%d", &x, &y);
 53             map[x][y] = 1;
 54         }
 55         scanf("%d", &t);
 56         while (t--)
 57         {
 58             scanf("%d%d", &x, &y);
 59             map[x][y] = -1;
 60         }
 61 
 62         row_num = 0;
 63         for (int i = 1; i <= n; i++)
 64         {
 65             bool flag = true;
 66             for (int j = 1; j <= m; j++)
 67             {
 68                 if (map[i][j] == 1)
 69                 {
 70 
 71                     if (flag)  row_num++;
 72                     g[i][j].first = row_num;
 73                     flag = false;
 74                 }
 75                 if (map[i][j] == -1)
 76                     flag = 1;
 77             }
 78         }
 79 
 80         col_num = 0;
 81         for (int j = 1; j <= m; j++)
 82         {
 83             bool flag = true;
 84             for (int i = 1; i <= n; i++)
 85             {
 86                 if (map[i][j] == 1)
 87                 {
 88                     if (flag)  col_num++;
 89                     g[i][j].second = col_num;
 90                     flag = false;
 91                 }
 92                 if (map[i][j] == -1)
 93                     flag = true;
 94             }
 95         }
 96         for (int i = 1; i <= n;i++)
 97         for (int j = 1; j <= m;j++)
 98         if (map[i][j] == 1)   G[g[i][j].first][g[i][j].second] = 1;
 99         int ans = 0;
100         for (int i = 1; i <= row_num; i++)
101         {
102             memset(vis, 0, sizeof(vis));
103             if (dfs(i))  ans++;
104         }
105         printf("%d
", ans);
106     }
107     return 0;
108 }