【图论】POJ 3020 Antenna Placement

这段时间要沉迷刷题一段时间了，就让****陪我一起吧！

一、题目大意

一个矩形中，有N个城市’*’，现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。

问至少放置多少个基站才能使得所有的城市都覆盖无线？

二、题目思路以及AC代码

这道题如果没有基础的话还真是挺难想到的，但如果你了解过匈牙利算法，了解过最小点覆盖和最小边覆盖，那这道题还是挺有意思的。

匈牙利算法

匈牙利算法是用来求解二分图最大匹配的经典算法，之前我也进行过总结，如果有同学不了解的话，可以直接去看，下面是我相应的博文链接。
【图论】匈牙利算法入门

最小点覆盖

这里我只给大家陈述概念，也会给一些简易的证明，但因为只是为了帮助大家理解问题，所以不会太严谨，大牛勿喷。

最小点覆盖，其实就是需要在二分图中寻找一个点集，让这个点集中的点，可以覆盖二分图中全部的边。那怎么样才能叫覆盖边了呢？就是如果有一条边(u, v)，端点是u和v，那么这里u和v中任意一点都覆盖了这条边。

下面给出计算公式，在二分图中：

最小点覆盖数目 = 二分图最大匹配数目

这个我这里就不证明了，因为理论也比较简单，对于初学者来说，背过就完事了。

最小边覆盖

最小边覆盖，其实和最小点覆盖类似，就是需要在二分图中寻找一个边集，让这个边集中的边，可以覆盖二分图中全部的点。这里就有一个同样的问题，怎么才能叫覆盖点了呢？就是如果有一条边(u，v)，端点是u和v，那么说这条边覆盖了点u和v。

下面也给出最小边覆盖的计算公式，在二分图中：

最小边覆盖数目 = 总顶点数目 - 二分图最大匹配数目
这个公式我还是稍微帮大家理解一下吧，毕竟一会也会用到。我们可以简单的这样来理解，对于一个二分图，最大匹配求出的是什么，是一系列的边，这些边不会重复从一个顶点引出，什么意思呢？就是说，最大匹配对应的那些边，他们都是覆盖两个顶点的，如果这里不理解，就停下来好好琢磨一下。

然后我们继续，既然都说是最大匹配了，那除了最大匹配，剩下的边，若覆盖顶点的话，就肯定只能每条边覆盖一个顶点了，这样我们设几个变量来更好的说明问题。首先设最大匹配数目为m，总顶点数为n，设除了最大匹配对应的边覆盖的点之外，剩下的那些顶点的数目为a。这样的话我们的最小边覆盖数目就是m + a，因为m + a是我们最好的进行边覆盖的方法，也肯定是最小的。而全部顶点的数目是n = 2*m + a，最大匹配边每条对应两个顶点，其余每个对应一个顶点。从而得到 n - m就是我们的最小边覆盖，也就是上文提到的公式了。

这一部分如果有不明白的同学一定要想清楚，因为后面会用到，大家可以在评论区提问，我会尽快回答的。

题目思路

说完了概念，下面进入我们这个题目，题目要求覆盖所有城市的最小基站数目，而每个基站只能覆盖2个城市，这不就是标准的最小边覆盖吗？

我们只需要这样建图即可：

首先用每个城市作为顶点，但这里需要有一个技巧，拆点，说起来很高大上，其实就是把同一个城市画成两个顶点，一个作为二分图的第一类点，一个作为二分图的第二类点，因为我们要对二分图的两类点进行连线，所以必须强行构造。
然后，对于相邻的城市，把其在图中对应的一类点和二类点连接起来。
建图完成

如数据

2 2
**
**

建图如下：
【图论】POJ 3020 Antenna Placement
建完图之后，剩下的工作就比较简单了，就是求取图的最大匹配，然后利用 n - m的公式求解。

但有一点需要注意的是，我们要在 n - m对m取值的时候，取最大匹配数除以2，因为我们在之前进行了拆点的操作。这里可以参照上图，可以观察到上图都是对称的，但其实我们如果对上图直接进行最大匹配求解的话是有些多余的东西的，比如1 - 2 和 2 - 1这两条边，对于我们的实际问题来说，只需要考虑其中一条就行了，因为基站覆盖 1和2 城市和基站覆盖 2和1 城市是一样的效果，这也是我们为什么除以2的原因。

这里我很不赞同有些题解说是因为无向图的原因，虽然确实也是因为它是无向图，但容易误导初学者，我甚至怀疑他们自己都还不知道原因就在写题解。

好啦，该说的都说完啦! 下面给出AC代码：

#include <iostream>
#define MAXN 405
using namespace std;

int H, W;
int N;

int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };

bool lines[MAXN][MAXN];
char map[45][15];
int fmap[45][15];
int divide[MAXN];
bool vis_div[MAXN];

void init() {
	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++) {
			lines[i][j] = false;
		}
		divide[i] = 0;
		vis_div[i] = false;
	}

	for (int i = 0; i < 45; i++) {
		for (int j = 0; j < 45; j++) {
			fmap[i][j] = 0;
		}
	}
}

bool find(int x) {
	for (int i = 1; i <= N; i++) {
		if (!vis_div[i] && lines[x][i]) {
			vis_div[i] = true;

			if (divide[i] == 0 || find(divide[i])) {
				divide[i] = x;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int T;
	scanf("%d", &T);

	while (T--) {
		init();

		scanf("%d%d", &H, &W);

		int cnt = 0;
		getchar();
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				scanf("%c", &map[i][j]);
				if (map[i][j] == '*')
					fmap[i][j] = ++cnt;
			}
			getchar();
		}

		N = cnt;

		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				if (fmap[i][j]) {

					for (int k = 0; k < 4; k++) {
						int nx = i + dx[k];
						int ny = j + dy[k];

						if (nx <= 0 || nx > H || ny <= 0 || ny > W) continue;
						if (fmap[nx][ny])
							lines[fmap[i][j]][fmap[nx][ny]] = true;
					}

				}
			}
		}

		int match = 0;
		for (int i = 1; i <= N; i++) {
			for (int i = 0; i < MAXN; i++) {
				vis_div[i] = false;
			}
			if (find(i)) match++;
		}

		printf("%d\n", N - match/2);
	}

    return 0;
}

如有问题，欢迎大家指正！！！