TJOI2016 游戏

TJOI
二分图

TJOI2016 游戏

题目大意：

给定一张n ∗ m的网格地图:

其中∗代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。

x代表软石头，炸弹的威力可以穿透，不能在此放置炸弹。

#代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。

现在任意给出一张n ∗ m的网格地图，问你最多能放置多少炸弹。

题解：

首先我们不考虑有石头的存在。

考虑构图，把行列看做节点，行列的交点看做两个节点间的边。

如果有一个炸弹放在一个交点上，我们可以想象成选中了连接在这一行与这一列之间的边。

那么一行、一列不能放多个炸弹的条件，就转换成为一个节点不能有多条被选中的边。

那么很显然，题目就转化为最大匹配了。

又因为，只有行列之间存在边，不难发现，这是一个二分图。

那么再来考虑有石头的存在。

硬石头的作用无非是，把一个节点拆成若干个节点。

软石头的作用无非是，使某行某列这两个节点间的边无法连上。

对于最终构出来的图，我们跑一下匈牙利算法即可得到答案。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=55;
int n,m,L[N][N],R[N][N],cnt;
char str[N][N];
int tot_edge,head[N*N*2],link[N*N*2],used[N*N*2];
struct Edge{
	int to,nxt;
}edge[N*N];
void add_edge(int a,int b){
	edge[tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge++;
}
bool dfs(int p){
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(used[to])continue;
		used[to]=true;
		if(!link[to]||dfs(link[to])){
			link[to]=p;
			return true;
		}
	}
	return false;
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",str[i]+1);
	for(int i=1;i<=n;i++){
		cnt++;
		bool flag=0;
		for(int j=1;j<=m;j++){
			if(str[i][j]=='#'){
				if(flag)cnt++,flag=0;
			}else L[i][j]=cnt,flag=1;
		}
		if(!flag)cnt--;
	}
	for(int j=1;j<=m;j++){
		cnt++;
		bool flag=0;
		for(int i=1;i<=n;i++){
			if(str[i][j]=='#'){
				if(flag)cnt++,flag=0;
			}else  R[i][j]=cnt,flag=1;
		}
		if(!flag)cnt--;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(str[i][j]=='*')add_edge(L[i][j],R[i][j]);
		}
	}
	int ans=0;
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=cnt;j++)used[j]=0;
		if(dfs(i))ans++;
	}
	printf("%d\n",ans);
	return 0;
}
分享到 评论