H - Antenna Placement POJ - 3020（最小边覆盖）

题目链接
解题思路：

• 最小边覆盖 = 总点数 - 最大匹配数

AC代码：

// Test1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
//最小边覆盖，而且最小边覆盖 = 总点数(cnt) - 最大匹配数(ans / 2) ，因为是双向图
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 50;
int T, h, w, cnt;
char a[maxn][maxn];
int match[1010], vis[1010];
int id[maxn][maxn], graph[1010][1010];
void init() {
	cnt = 0;
	cin >> h >> w;
	for (int i = 1; i <= h; i++)
		cin >> a[i] + 1;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			if (a[i][j] == '*')
				id[i][j] = ++cnt;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++) {
			if (a[i][j] != '*') continue;
			if (a[i - 1][j] == '*') graph[id[i][j]][id[i - 1][j]] = 1;
			if (a[i + 1][j] == '*') graph[id[i][j]][id[i + 1][j]] = 1;
			if (a[i][j - 1] == '*') graph[id[i][j]][id[i][j - 1]] = 1;
			if (a[i][j + 1] == '*') graph[id[i][j]][id[i][j + 1]] = 1;
		}
}
bool dfs(int x, int num) {
	for (int i = 1; i <= cnt; i++) {
		if (graph[x][i] && vis[i] != num) {
			vis[i] = num;
			if (!match[i] || dfs(match[i], num)) {
				match[i] = x;
				return true;
			}
		}
	}
	return false;
}
int maxmatch() {
	int sum = 0, num = 0;
	for (int i = 1; i <= cnt; i++) {
		if (dfs(i, ++num)) sum += 1;
	}
	return sum;
}
void aftermath() {
	for (int i = 1; i <= cnt; i++) vis[i] = match[i] = 0;
	for (int i = 1; i <= cnt; i++)
		for (int j = 1; j <= cnt; j++)
			graph[i][j] = 0;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			id[i][j] = 0, a[i][j] = '0';
}
int main() {
	ios::sync_with_stdio(false);
	cin >> T;
	while (T--) {
		init();
		int ans = maxmatch();
		ans = cnt - ans / 2;
		cout << ans << endl;
		aftermath();
	}
	return 0;
}

本文地址：https://blog.csdn.net/weixin_45691711/article/details/107280972