POJ3020

原题：http://poj.org/problem?id=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; }