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; }
|