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

[[在线等球解释]]为什么注释掉的dfs两次的方法不对?0边也试过了。。

Posted by 511818218 at 2013-09-22 20:29:33 on Problem 3204
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=50005;
int head[515],lv[515],ver[N],next[N],f[N],tot,S,T,Q[N];
bool v[515];

void add(int x,int y,int z)
{
	ver[++tot]=y,f[tot]=z,next[tot]=head[x],head[x]=tot;
	ver[++tot]=x,f[tot]=0,next[tot]=head[y],head[y]=tot;
}

bool tell()
{
	int i,x,y,l=0,r=0;
	memset(lv,-1,sizeof(lv));
	lv[Q[0]=S]=0;
	while(l<=r)
	{
		x=Q[l++];
		for(i=head[x];i!=-1;i=next[i])
			if(lv[y=ver[i]]==-1&&f[i])
				lv[y]=lv[x]+1,Q[++r]=y;
	}
	if(lv[T]==-1) return 0;
	return 1;
}

int zeng(int x,int less)
{
	if(x==T) return less;
	int r,use=0,i,y;
	for(i=head[x];i!=-1&&less;i=next[i])
		if(lv[y=ver[i]]==lv[x]+1&&f[i])
			r=zeng(y,min(less,f[i])),use+=r,less-=r,f[i]-=r,f[i^1]+=r;
	if(!use) lv[x]=-1;
	return use;
}

int dinic()
{
	int sum=0;
	while(tell()) sum+=zeng(S,0x7f7f7f7f);
	return sum;
}
/*
void dfs(int x,int p)
{
	v[x]=1;
	int i;
	for(i=head[x];i!=-1;i=next[i])
	{
		if(i%2==p&&f[i^p]&&!v[ver[i]]) dfs(ver[i],p);
	}
	return ;
}
*/
int main()
{
	memset(head,-1,sizeof(head));
	tot=-1;
	int i,x,y,z,ans=0,n,m;
	scanf("%d%d",&n,&m);
	S=0,T=n-1;
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&x,&y,&z),add(x,y,z);
	dinic();
	/*
	dfs(S,0);
	dfs(T,1);
	for(i=0;i<=tot;i+=2)
		if(!f[i]&&v[ver[i]]&&v[ver[i^1]])
			ans++,cout<<ver[i]<<' '<<ver[i^1]<<endl;
	*/
	for(i=0;i<=tot;i+=2)
	{
		if(!f[i])
		{
			f[i]++;
			if(tell())ans++;
			f[i]--;
		}
	}
	
	printf("%d",ans);
}

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