首页 > 代码库 > HDU5093【最大流】
HDU5093【最大流】
题意：在*上建设炮塔，炮塔会像上下左右4个方向发射炮弹。o为浮冰，炮弹会越过。#为冰山，会阻挡炮弹。建设的炮塔会相互攻击，问最多建设多少个不互相攻击的炮塔。
本来我以为是贪心的，就像http://acm.hdu.edu.cn/showproblem.php?pid=1045一样，结果WA了，不懂是写错还是非法不行。
后来改成用http://acm.hdu.edu.cn/showproblem.php?pid=1045的网络流方法做就AC了。
建图：先用#把整个地图围一圈，把所有点分成ab两种点，源点向a建边，b点向汇点建边。对地图上的所有*，找它左端第一个#设为A，上端第一个#设为B，A的a点向B的b点建边。所建边容量都为1.
#include<iostream>#include<cstdio>#include<queue>using namespace std;const int NO=57;const int INF=1000000000;struct X{ int x,y; X(){x=y=0;} X(int a,int b){x=a;y=b;}}map[NO][NO],u[NO*NO*4],v[NO*NO*4],st,ed,r[NO][NO],c[NO][NO];char MAP[NO][NO];int n,m;int first[NO*2][NO*2],next[NO*NO*4],w[NO*NO*4],num;int dis[NO*2][NO*2];int ans[NO][NO];void reset_first(){ int i,j; num=0; for(i=0;i<=ed.x;i++) for(j=0;j<=ed.y;j++) first[i][j]=-1;}void add(int x1,int y1,int x2,int y2,int c){ u[num].x=x1,u[num].y=y1; v[num].x=x2,v[num].y=y2; w[num]=c; next[num]=first[x1][y1]; first[x1][y1]=num++; u[num].x=x2,u[num].y=y2; v[num].x=x1,v[num].y=y1; w[num]=0; next[num]=first[x2][y2]; first[x2][y2]=num++;}void reset_dis(){ int i,j; for(i=0;i<=ed.x;i++) for(j=0;j<=ed.y;j++) dis[i][j]=-1;}bool bfs(){ int i; X a; reset_dis(); queue<X> t; t.push(st); dis[st.x][st.y]=0; while(!t.empty()) { a=t.front(); t.pop(); for(i=first[a.x][a.y];i!=-1;i=next[i]) if(w[i]&&dis[v[i].x][v[i].y]==-1) { dis[v[i].x][v[i].y]=dis[a.x][a.y]+1; t.push(v[i]); } } return dis[ed.x][ed.y]!=-1;}int min(int a,int b){return a<b?a:b;}int dfs(const X &k,int MIN){ if(k.x==ed.x&&k.y==ed.y) return MIN; int sum=0,a,i; for(i=first[k.x][k.y];i!=-1&&sum<MIN;i=next[i]) if(w[i]&&dis[v[i].x][v[i].y]==dis[k.x][k.y]+1&&(a=dfs(v[i],min(MIN-sum,w[i])))) { w[i]-=a; w[i^1]+=a; sum+=a; } if(!sum) dis[k.x][k.y]=-1; return sum;}int DANIC(){ int ans=0,a; while(bfs()) while(a=dfs(st,INF)) ans+=a; return ans;}void read(){ for(int i=0;i<=n+1;i++) MAP[i][0]=MAP[i][m+1]=‘#‘; for(int j=0;j<=m+1;j++) MAP[0][j]=MAP[n+1][j]=‘#‘; for(int i=1;i<=n;i++) { getchar(); for(int j=1;j<=m;j++) MAP[i][j]=getchar(); } for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++) if(MAP[i][j]==‘#‘) { ans[i][j]=-1; map[i][j].x=MAP[i+1][j]!=‘#‘; map[i][j].y=MAP[i][j+1]!=‘#‘; } else ans[i][j]=map[i][j].x=map[i][j].y=0;}void build(){ int i,j,k; for(i=0;i<=n;i++) for(j=0;j<=m;j++) { if(map[i][j].x) { for(k=0;i+k+1<=n;k++) if(ans[i+k+1][j]==-1) break; else c[i+k+1][j].x=i,c[i+k+1][j].y=j; add(n+i,m+j,ed.x,ed.y,1); } if(map[i][j].y) { for(k=0;j+k+1<=m;k++) if(ans[i][j+k+1]==-1) break; else r[i][j+k+1].x=i,r[i][j+k+1].y=j; add(st.x,st.y,i,j,1); } } for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(MAP[i][j]==‘*‘) add(r[i][j].x,r[i][j].y,n+c[i][j].x,m+c[i][j].y,1);}int main(){ int ttt; scanf("%d",&ttt); while(ttt--) { scanf("%d%d",&n,&m); ed.x=n*2+1;ed.y=m*2+1; reset_first(); read(); build(); printf("%d\n",DANIC()); } return 0;}
HDU5093【最大流】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。