POJ3020 二分图匹配

2017年7月29日

给你一个平面图上,图上有城市和空地,城市用 * 表示,空地用 o 表示,让你建设最少数量的基站来覆盖所有城市.一个基站可以覆盖上下相邻,或者左右相邻的两个城市.求建设基站的数量.

二分图的最小路径覆盖问题.将相邻的两个城市间连一条边,那么所要求的就是至少有多少条边,能够把所有城市都覆盖.(如果一个城市周围都没有其它城市,那不就是没有边跟它相连?)

拿组简单的数据分析下:

oooo
*o*o
o**o

对于上面这组数据的城市,给它标号为:

oooo
1o2o
o34o

拆点,建立如下的二分图(没把边画出来):
1 1′

2 2′

3 3′

4 4′
其中,2 跟 4′ 相连, 3跟 4’相连,4跟2’相连,4跟3’相连.

可以根据图中易得匹配数(记为 k)为2(2->4’,4->2’),匹配数 / 2 = 基站数量,就是说用了一条边(基站)匹配了两个城市,总共有 cnt 个城市,剩下还有 cnt – k 个城市,这剩下的城市就得自己建设一个基站给自己,剩下的城市总共建设了 cnt – k 个基站,所以最终答案总共建设了 cnt - k + k / 2个基站.(最小路径覆盖问题)

要注意区分最小路径覆盖跟最小点覆盖.

最小路径覆盖:用最少的边覆盖所有的点.其结果等于(顶点数-二分图最大匹配数/2).

最小点覆盖:用最少的点覆盖所有边.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int w, h;
char mp[50][50];
int rec[50][50];
vector<int> G[405];
int vis[405];
int match[405];
bool dfs(int u)
{
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (vis[v])
            continue;
        vis[v] = 1;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &h, &w);
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            scanf("%s", mp[i]);
            for (int j = 0; j < w; j++) {
                if (mp[i][j] == '*')
                    rec[i][j] = cnt++;
            }
        }
        for (int i = 0; i <= cnt; i++)
            G[i].clear();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (mp[i][j] == '*') {
                    for (int k = 0; k < 4; k++) {
                        int nx = dx[k] + i, ny = dy[k] + j;
                        if (0 <= nx && nx < h && 0 <= ny && ny < w && mp[nx][ny] == '*') {
                            int u = rec[i][j], v = rec[nx][ny];
                            G[u].push_back(v);
                        }
                    }
                }
            }
        }
        int tmp = 0;
        memset(match, -1, sizeof(match));
        for (int i = 0; i < cnt; i++) {
            memset(vis, 0, sizeof(vis));
            tmp += dfs(i);
        }
        printf("%d\n", cnt - tmp / 2);
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注