前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >POJ 3020 Antenna Placement(二分图最小边覆盖)

POJ 3020 Antenna Placement(二分图最小边覆盖)

作者头像
Ch_Zaqdt
发布2019-01-10 16:12:28
7030
发布2019-01-10 16:12:28
举报
文章被收录于专栏:Zaqdt_ACM

题目链接:http://poj.org/problem?id=3020

       题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的大小,问最少需要安装多少个基站。

       正解就是去求无向图的最小边覆盖,因为我们可以把每个城市记一个编号,然后将相邻的两个城市进行建边,这个一条边就相当于一个基站,然后去求最少要用多少条边去覆盖城市,所以就是一个最小边覆盖的问题了,而无向图的最小边覆盖=节点数-最大匹配数/2。这道题的难点其实是怎么去建图,前两天刚写了一道类似的题,而那道题是求最大匹配数的,但是存图方法跟这道题一模一样,想看的可以看看:HDU 4185 Oil Skimming(思维+二分图最大匹配数)


AC代码:

代码语言:javascript
复制
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#define maxn 55
using namespace std;
struct Node{
	int to,next;
}Edge[maxn * maxn];
int head[maxn * maxn], num;
string str[maxn];
int a[maxn][maxn];
int pre[maxn * maxn];
bool vis[maxn * maxn];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int T,n,m,cnt;

void init(){
	memset(head,-1,sizeof(head));
	memset(a,0,sizeof(a));
	num = 0;
}

void add(int u,int v){
	Edge[num].to = v;
	Edge[num].next = head[u];
	head[u] = num ++;
}

bool OK(int x,int y){
	if(x < 0 || y < 0 || x >= n || y >= m)return false;
	if(str[x][y] != '*') return false;
	return true;
}

bool dfs(int u){
	for(int i=head[u];i!=-1;i=Edge[i].next){
		int v = Edge[i].to;
		if(vis[v] == false){
			vis[v] = true;
			if(pre[v] == -1 || dfs(pre[v])){
				pre[v] = u;
				return true;
			}
		}
	}
	return false;
}

int solve(){
	int sum = 0;
	memset(pre,-1,sizeof(pre));
	for(int i=1;i<=cnt;i++){
		memset(vis,false,sizeof(vis));
		if(dfs(i)) sum ++;
	}
	return sum;
}

int main()
{
	scanf("%d",&T);
	while(T--){
		init();
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++){
			cin>>str[i];
		}
		cnt = 1;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(str[i][j] == '*'){
					a[i][j] = cnt ++;
				}
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(str[i][j] == '*'){
					for(int k=0;k<4;k++){
						int xx = i + dir[k][0];
						int yy = j + dir[k][1];
						if(OK(xx, yy)){
							add(a[xx][yy], a[i][j]);
							add(a[i][j], a[xx][yy]);
						}
					}
				}
			}
		}
		int ans = solve();
		printf("%d\n", cnt - ans / 2 - 1);
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年11月27日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档