POJ3020

POJ3020

原题：=3020

题目大意：

有四种天线，分别可以朝四个方向覆盖一个城镇（place of interest）（可以看成一个天线可以覆盖两个城镇），给出一张图，星号代表城镇，空格代表空地，问最少需要多少天线可以覆盖所有的城镇。

思路：

node标记点并且给城镇编号，edge标识出城镇与城镇的相邻关系，构建一个无向图。其中，点代表城镇，边代表连接的两个城镇中，只有一个需要安装天线

-> 点的数量=最多需要安装多少天线

-> 尽量用边连接不重复的点

-> 二分图的最大匹配（相关知识）

注意：构造的图为无向图，匹配数量应该减半！因为结果而node_num - maxMatch()/2;

#include <iostream>
using namespace std;char map[41][11];
int h, w;
int node[41][11];
bool edge[405][405];
int nn = 0;
bool vis[405];
int match[405];int path(int u) {for (int v = 1; v <= nn; ++v) {if (!vis[v] && edge[u][v]) {vis[v] = 1;if (match[v] == -1 || path(match[v])) {match[v] = u;return 1;}}}return 0;
}int maxMatch() {int res = 0;memset(match, -1, sizeof(match));for (int u = 1; u <= nn; ++u) {memset(vis, 0, sizeof(vis));if (path(u))res++;}return res;
}
int main() {int S;cin >> S;while (S--) {cin >> h >> w;nn = 0;memset(node, 0, sizeof(node));memset(edge, 0, sizeof(edge));for (int i = 1; i <= h; ++i) {for (int j = 1; j <= w; ++j) {cin >> map[i][j];if (map[i][j] == '*')node[i][j] = ++nn; //记录点并且编号}}int tmp;//构造邻接矩阵，表示城镇之间的相邻关系for (int i = 1; i <= h; ++i) {for (int j = 1; j <= w; ++j) {tmp = node[i][j];if (tmp > 0) {if (i > 1) {if (node[i - 1][j] > 0)edge[tmp][node[i - 1][j]] = 1;}if (i < h) {if (node[i + 1][j] > 0)edge[tmp][node[i + 1][j]] = 1;}if (j > 1) {if (node[i][j - 1] > 0)edge[tmp][node[i][j - 1]] = 1;}if (j < w) {if (node[i][j + 1] > 0)edge[tmp][node[i][j + 1]] = 1;}}}}//求最大匹配，参看上文二分图最大匹配的相关知识（连接）cout << nn - maxMatch()/2 << endl;}return 0;
}