Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

跪拜求神牛讲解1815~~~在下初学最大流,总是调不对。麻烦看看是不是思路有问题,还是代码实现有问题。

Posted by Liuyanzhi at 2011-12-24 16:47:17 on Problem 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator