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