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

题意：

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

思路：

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

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<cstring>

 using namespace std;

 const int maxn =  + ;

 int n, m;

 int row_num, col_num;

 int map[maxn][maxn];

 int G[maxn][maxn];

 int match[maxn];

 int vis[maxn];

 pair<int, int> g[maxn][maxn];

 bool dfs(int u)

 {

     for (int j = ; j <= col_num; j++)

     {

         if (!vis[j] && G[u][j])

         {

             vis[j] = ;

             if (match[j] == - || dfs(match[j]))

             {

                 match[j] = u;

                 return true;

             }

         }

     }

     return false;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     while (T--)

     {

         scanf("%d%d", &n, &m);

         memset(map, , sizeof(map));

         memset(G, , sizeof(G));

         memset(match, -, sizeof(match));

         int t, x, y;

         scanf("%d", &t);

         while (t--)

         {

             scanf("%d%d", &x, &y);

             map[x][y] = ;

         }

         scanf("%d", &t);

         while (t--)

         {

             scanf("%d%d", &x, &y);

             map[x][y] = -;

         }

         row_num = ;

         for (int i = ; i <= n; i++)

         {

             bool flag = true;

             for (int j = ; j <= m; j++)

             {

                 if (map[i][j] == )

                 {

                     if (flag)  row_num++;

                     g[i][j].first = row_num;

                     flag = false;

                 }

                 if (map[i][j] == -)

                     flag = ;

             }

         }

         col_num = ;

         for (int j = ; j <= m; j++)

         {

             bool flag = true;

             for (int i = ; i <= n; i++)

             {

                 if (map[i][j] == )

                 {

                     if (flag)  col_num++;

                     g[i][j].second = col_num;

                     flag = false;

                 }

                 if (map[i][j] == -)

                     flag = true;

             }

         }

         for (int i = ; i <= n;i++)

         for (int j = ; j <= m;j++)

         if (map[i][j] == )   G[g[i][j].first][g[i][j].second] = ;

         int ans = ;

         for (int i = ; i <= row_num; i++)

         {

             memset(vis, , sizeof(vis));

             if (dfs(i))  ans++;

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

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

最新文章

热门文章