Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
跪拜求神牛讲解1815~~~在下初学最大流,总是调不对。麻烦看看是不是思路有问题,还是代码实现有问题。#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int Max=0xfffffff,SIZE=1024; struct node{int to,next,v,op;}edge[SIZE*SIZE]; int pn,n,st,end,cnt,dist[SIZE],sumd[SIZE],pre[SIZE],h[SIZE],now[SIZE],ret[SIZE],Maxflow; int map[SIZE][SIZE],mark[SIZE],output[SIZE]; void Init() { int i,j; scanf("%d%d%d",&n,&st,&end); pn=n; n*=2; st+=pn,end+=pn; for(i=1;i<=pn;i++) for(j=1;j<=pn;j++) scanf("%d",&map[i][j]); } int SAP() { int i,to,t,ans=0,flow=Max,minn,tmp; bool flag; for(i=1;i<=n;i++) now[i]=h[i]; i=st,sumd[0]=n; while(dist[st]<n) { ret[i]=flow,flag=false; for(t=now[i];t;t=edge[t].next) { to=edge[t].to; if(edge[t].v>0&&dist[to]+1==dist[i]) { flag=true; now[i]=t; if(flow>edge[t].v) flow=edge[t].v; pre[to]=t; i=to; if(i==end) { ans+=flow; while(i!=st) { edge[pre[i]].v-=flow; edge[edge[pre[i]].op].v+=flow; i=edge[edge[pre[i]].op].to; } flow=Max; } break; } } if(flag)continue; minn=n; t=h[i]; for(t=h[i];t;t=edge[t].next) if(edge[t].v>0&&dist[edge[t].to]<minn) minn=dist[edge[t].to],tmp=t; now[i]=tmp; sumd[dist[i]]--; if(sumd[dist[i]]==0)break; dist[i]=minn+1; sumd[dist[i]]++; if(i!=st) i=edge[edge[pre[i]].op].to,flow=ret[i]; } //cout<<ans<<endl; return ans; } void Memset() { memset(sumd,0,sizeof(sumd)); memset(edge,0,sizeof(edge)); memset(dist,0,sizeof(dist)); memset(pre,0,sizeof(pre)); memset(ret,0,sizeof(ret)); memset(h,0,sizeof(h)); cnt=0; } void add(int x,int y,int v) { cnt++,edge[cnt].to=y,edge[cnt].v=v,edge[cnt].op=cnt+1;edge[cnt].next=h[x];h[x]=cnt; cnt++,edge[cnt].to=x,edge[cnt].v=0,edge[cnt].op=cnt-1;edge[cnt].next=h[y];h[y]=cnt; } void Make_edge() { int i,j; Memset(); for(i=1;i<=pn;i++)if(!mark[i])add(i,i+pn,1); for(i=1;i<=pn;i++) { if(mark[i]==1)continue; for(j=i+1;j<=pn;j++) { if(mark[j]==1||map[i][j]==0)continue; add(i+pn,j,Max),add(j+pn,i,Max); } } } int main() { int i,t; Init(); if(map[st][end]==1){printf("NO ANSWER!\n");return 0;} Make_edge(); Maxflow=SAP(); if(Maxflow==0) { putchar('0'); return 0; } for(i=1;i<=pn;i++) { if(i==st-pn||i==end-pn)continue; mark[i]=1; Make_edge(); t=SAP(); if(Maxflow==t)mark[i]=0; else Maxflow=t; } for(i=1;i<=pn;i++)if(mark[i])output[++output[0]]=i; if(output[0]) { printf("%d\n%d",output[0],output[1]); for(i=2;i<=output[0];i++)printf(" %d",output[i]); } else putchar('0'); return 0; } 用的方法: 1、拆点 2、建边后先一次SAP求最大流 3、依次标记每一个点,重新建图,不建标记了的,一次SAP,看和上次答案是否相同,相同,则恢复标记,反之修改当前最大流,不恢复标记 4、输出答案 在下初学最大流,总是调不对。 跪拜求神牛~~~麻烦看看是不是思路有问题,还是代码实现有问题。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator