首页 > 代码库 > poj 3020 Antenna Placement 解题报告

poj 3020 Antenna Placement 解题报告

2024-07-18 07:03:25   216人阅读

题目链接：http://poj.org/problem?id=3020

题目意思：首先，请忽略那幅有可能误导他人成分的截图（可能我悟性差，反正有一点点误导我了）。

       给出一幅 h * w 的图，  “ * ” 表示 point of interest，“ o ” 忽略之。你可以对 " * " （假设这个 “* ”的坐标是 (i, j)）画圈，每个圈只能把它四周的某一个点括住（或者是上面(i-1, j) or 下面(i+1, j) or 左边(i, j-1)  or 右边(i, j+1)），也就是说，这个圈 只能覆盖两个 “ * ” 点。问最少需要多少个这样的圈 来括住所有的 " * "。

      这题实质上求得是无向二分图的最小路径覆盖数，最关键的是建图！！！！

      还有就是需要知道一个公式：无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2

      参考了别人的建图方式，真是太强大了~~~~

      建图如下：每遇到一个 " * " 就记录这个 " * " 的编号，就好像7 9 这幅图的第二行，它的 " * " 依次的编号是3 4 5 6，因为第一行的 “ *”  已经把编号1， 2用了，实质代表这个 " * " 是第 几 个 point of interest。接着对每个 " * " （假设编号为 i ）遍历它的四个方向，如果它的某个方向也有 " * " （编号为 j）， 那么就将 i 和 j 连边。

      最后匈牙利模板求匹配数，至于总的编号数就是公式中的顶点数，套入公式，大功告成也 ^_^........

     

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 500 + 10; 7  8 int vis[maxn], match[maxn]; 9 int map[maxn][maxn], mark[maxn][maxn];10 int cnt, maxmatch;     // cnt: 顶点数  maxmatch：最大匹配数11 12 int dx[] = {0, 0, 1, -1};13 int dy[] = {1, -1, 0, 0};14 15 int dfs(int x)16 {17     for (int i = 1; i <= cnt-1; i++)18     {19         if (!vis[i] && map[x][i])20         {21             vis[i] = 1;22             if (!match[i] || dfs(match[i]))23             {24                 match[i] = x;25                 return 1;26             }27         }28     }29     return 0;30 }31 32 void Hungary()33 {34     maxmatch = 0;35     for (int i = 1; i <= cnt-1; i++)36     {37         memset(vis, 0, sizeof(vis));38         maxmatch += dfs(i);39     }40 }41 42 int main()43 {44     int T, h, w;45     while (scanf("%d", &T) != EOF)46     {47         while (T--)48         {49             scanf("%d%d", &h, &w);50             char ch;51             cnt = 1;52             memset(mark, 0, sizeof(mark));53             memset(map, 0, sizeof(map));54             memset(match, 0, sizeof(match));55 56             for (int i = 0; i < h; i++)57             {58                 for (int j = 0; j < w; j++)59                 {60                     cin >> ch;61                     if (ch == ‘*‘)62                     {63                         mark[i][j] = cnt;64                         cnt++;65                     }66                 }67             }68             for (int i = 0; i < h; i++)69             {70                 for (int j = 0; j < w; j++)71                 {72                     if (mark[i][j])73                     {74                         int tmp = mark[i][j];     // 当前"*"编号75                         for (int k = 0; k < 4; k++)   // 遍历它的四个方向76                         {77                             int ti = i + dx[k];78                             int tj = j + dy[k];79                             if (ti >= 0 && ti < 40 && tj >= 0 && tj < 10 && mark[ti][tj] > 0)80                                 map[tmp][mark[ti][tj]] = 1;81                             }82                         }83                     }84                 }85             }86             Hungary();87             printf("%d\n", cnt-1-maxmatch/2);88         }89     }90     return 0;91 }

 


联系
我们