欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

H - Antenna Placement POJ - 3020(最小边覆盖)

程序员文章站 2022-03-22 08:39:38
题目链接解题思路:最小边覆盖 = 总点数 - 最大匹配数AC代码:// Test1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。////最小边覆盖,而且最小边覆盖 = 总点数(cnt) - 最大匹配数(ans / 2) ,因为是双向图#include #include #include #include #include

题目链接
解题思路:

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

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

上一篇: 92 反转链表 II

下一篇: vector_insert