#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=720055,INF=0x5f5f5f5f;
int S,T,tot,head[7055],next[N],ver[N],lv[7055],Q[N];
long long f[N];
void add(int x,int y,long long 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,s,y,l=0,r=0;
	memset(lv,-1,sizeof(lv));
	lv[Q[0]=S]=0;
	while(l<=r)
	{
		s=Q[l++];
		for(i=head[s];i!=-1;i=next[i])
			if(lv[y=ver[i]]==-1&&f[i]>0)
				lv[y]=lv[s]+1,Q[++r]=y;
	}
	if(lv[T]==-1) return 0;
	return 1;
}

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

long long dinic()
{
	long long sum=0;
	while(tell()) sum+=zeng(S,INF);
	return sum;
}

int main()
{
	int n,m,i,x,y,numedge=0,fullflow=0;
	long long a,maxflow;
	scanf("%d%d",&n,&m);
	S=0,T=n+1;
	memset(head,-1,sizeof(head));
	tot=-1;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a);
		if(a>0)
		{
			fullflow+=a;
			numedge++;
			add(S,i,a*10000-1);
		}
		else
			add(i,T,-a*10000+1);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y,INF);
	}
	maxflow=dinic();
	printf("%lld %lld",(maxflow+numedge)%10000,fullflow-(maxflow+numedge)/10000);
}

• Re:用放大边权的欢迎进来观摩下哪里Tle了。。 (57) 511818218 2013-09-22 21:08:27