#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=31000,maxm=8000000,oo=19930129;
int n1,m1,n,s,t,head[maxn],v[maxm],c[maxm],next[maxm],poi,pre[maxn],way[maxn];
void addedge(int a,int b,int w)
{
  v[++poi]=b;
  c[poi]=w;
  next[poi]=head[a];
  head[a]=poi;

  v[++poi]=a;
  c[poi]=0;
  next[poi]=head[b];
  head[b]=poi;
}
void datain()
{
  scanf("%d%d",&n1,&m1);
  n=n1+2;
  s=n1+1;
  t=s+1;
  poi=1;
  memset(head,0,sizeof(head));
  for(int i=1;i<=n1;++i){
	int c1,c2;
	scanf("%d%d",&c1,&c2);
	addedge(s,i,c1);
	addedge(i,t,c2);
  }
  for(int i=1;i<=m1;++i){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	addedge(a,b,c);
	addedge(b,a,c);
  }
}
int augment(int &vi)
{
  int x=vi,mint=oo,k;
  while(pre[x]){
	x=pre[x];
	if(c[way[x]]<=mint){
	  mint=c[way[x]];
	  k=x;
	}
  }
  x=vi;
  while(pre[x]){
	x=pre[x];
	c[way[x]]-=mint;
	c[way[x]^1]+=mint;
  }
  vi=s;
  return mint;
}
int isap()
{
  int flow=0,vx=s,d[maxn],gap[maxn];
  bool adv;
  pre[s]=0;
  memset(d,0,sizeof(d));
  memset(gap,0,sizeof(gap));
  gap[0]=n;
  memcpy(cur,head,sizeof(cur));
  while(d[s]<n){
	if(vx==t)flow+=augment(vx);
	adv=false;
	for(int i=head[vx];i;i=next[i])
	  if(d[v[i]]+1==d[vx]&&c[i]){
		pre[v[i]]=vx;
		way[vx]=i;
		vx=v[i];
		adv=true;
		break;
	  }
	if(adv)continue;
	else {
	  int mind=n;
	  for(int i=head[vx];i;i=next[i])
		if(c[i]&&v[i]!=vx)mind=min(mind,d[v[i]]+1);
	  if(--gap[d[vx]]==0)break;
	  d[vx]=mind;
	  ++gap[d[vx]];
	  if(vx!=s)vx=pre[vx];
	}
  }
  return flow;
}
int main()
{
#ifndef ONLINE_JUDGE
  freopen("p3469.in","r",stdin);
  freopen("p3469.out","w",stdout); 
#endif      
  datain();
  printf("%d\n",isap());
  return 0;
}

• Re:崩溃了。。我是sap，有gap优化。。就是不过呀。。。我加上current优化以后即死循环。。求指点 (12) talenth1 2011-08-06 01:05:34