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