首页 > 代码库 > HDU3338【最大流】
HDU3338【最大流】
建图：把所有点分成ab两种点，源点向a建边，b点向汇点建边。由源点向所有的abc/???（abc是数字）建边，容量为（abc-右边连续白点个数），由所有的???/abc（abc是数字）向汇点建边，容量为（abc-下边连续白点个数）。对所有白点，找它左端第一个黑点设为A，上端第一个黑点设为B，A的a点向B的b点建容量都为8的边。
跑一边最大流，把所有结果+1。
#include<iostream>#include<queue>using namespace std;const int NO=407;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];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(){ char s[10]; int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%s",s); if(s[0]==‘.‘) { map[i][j].x=map[i][j].y=0; ans[i][j]=0; continue; } ans[i][j]=-1; if(s[0]!=‘X‘) map[i][j].x=(s[0]-‘0‘)*100+(s[1]-‘0‘)*10+(s[2]-‘0‘); else map[i][j].x=0; if(s[4]!=‘X‘) map[i][j].y=(s[4]-‘0‘)*100+(s[5]-‘0‘)*10+(s[6]-‘0‘); else map[i][j].y=0; }}void build(){ int i,j,k; for(i=1;i<=n;i++) for(j=1;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,map[i][j].x-k); } 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,map[i][j].y-k); } } for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(ans[i][j]==0) add(r[i][j].x,r[i][j].y,n+c[i][j].x,m+c[i][j].y,8);}void PRINT(){ int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(map[i][j].y) for(k=first[i][j];k!=-1;k=next[k]) ans[i][v[k].y-m]=1+w[k+1]; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) if(ans[i][j]==-1) printf("_ "); else printf("%d ",ans[i][j]); puts(""); }}int main(){ while(scanf("%d%d",&n,&m)==2) { ed.x=n*2+1;ed.y=m*2+1; reset_first(); read(); build(); DANIC(); PRINT(); } return 0;}
HDU3338【最大流】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。