预流推进算法/code/c

#include <stdio.h>
const long MAX=10000;
struct point{long w,f;}net[MAX][MAX];
long s,t,q[MAX*10],head,tail,e[MAX],h[MAX];
struct node{long w,f;node *next;}p[MAX];
bool tt[MAX];
void init()
{
	long i,j;
	head=tail=0;
	for(i=s;i<=t;i++)tt[i]=e[i]=0,h[i]=0;
	h[s]=t+1;h[t]=0;
	for(i=s;i<=t;i++)
	{
		net[s][i].f=e[i]=net[s][i].w;
		net[i][s].f=-net[s][i].f;
		e[s]-=net[s][i].w;
		if(e[i]>0)
		{
			tt[i]=1;
			q[tail++]=i;
		}
	}
 
}
bool runflow(long u)
{
	long i;
	bool flag=0;
	for(i=s;i<=t;i++)
	{
		if(e[u]<=0)break;
		if(net[u][i].w-net[u][i].f>0&&h[u]==h[i]+1)
		{
			flag=1;
			long tmp=net[u][i].w-net[u][i].f<e[u]?net[u][i].w-net[u][i].f:e[u];
			net[u][i].f+=tmp;net[i][u].f=-net[u][i].f;
			e[u]-=tmp;e[i]+=tmp;
			if(!tt[i]&&i!=s&&i!=t&&e[i]>0)
			{
				q[tail++]=i;
				tt[i]=1;
			}
		}
	}
	return flag;
}
void relax(long u)
{
	long i,tmp=3*t,v=u;
	for(i=s;i<=t;i++)
	{
		if(i!=u&&h[i]<tmp&&net[u][i].w-net[u][i].f>0)
		{
			tmp=h[i];
			v=i;
		}
	}
	h[u]=h[v]+1;
}
long maxflow()
{
	init();
	long i;
	while(head<tail)
	{
		long u=q[head++];
		while(e[u]>0)
		{
			runflow(u);
			if(e[u]>0){
				relax(u);
			}
		}
		tt[u]=0;
	}
	long ans=0;
	for(i=s+1;i<=t;i++)ans+=net[s][i].f;
	return ans;
}
int main()
{
	long n,i,j,k,m;
	long a,b,c;
	while(scanf("%ld%ld",&n,&m)!=EOF)
	{
		s=0;t=n+1;
		for(i=s;i<=t;i++)for(j=s;j<=t;j++)net[i][j].w=net[i][j].f=0;
		for(i=1;i<=n;i++)
		{
			scanf("%ld%ld",&a,&b);
			net[s][i].w=a;net[i][t].w=b;
		}
		for(i=0;i<m;i++)
		{
			scanf("%ld%ld%ld",&a,&b,&c);
			net[a][b].w=net[b][a].w=c;
		}
		long ans=maxflow();
		printf("%ld\n",ans);
	}
	return 0;
}

预流推进与前向星

By JohnMave
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define QUERY 400
#define VMAX 500
 
typedef struct _str2	{
	int s;
	int t;
	int v;
}tmp;
 
int height[202],star[202];
int que[QUERY];
char inQ[202];
tmp iarc[402];
int flow[202];
int qh,qt;
 
int min(int a,int b)	{
	if(a<b)
		return a;
	return b;
}
 
void push(int u,tmp *arc,int vex)	{
	int i,fk;
	int v=arc->t;
	for(i=star[v];i<star[v+1]&&iarc[i].t!=u;i++)
	{;}
	fk=min(flow[u],(arc->v)-(arc->s));
	flow[u]-=fk;
	flow[v]+=fk;
	arc->s+=fk;
	iarc[i].s-=fk;
	if(!inQ[v]&&flow[v]>0&&v!=vex)
		{
			que[qt++]=v;
			qt%=QUERY;
			inQ[v]=1;
		}
}
 
void relabel(int u)	{
	int i;
	height[u]=VMAX;
	for(i=star[u];i<star[u+1];i++)
		if(iarc[i].v-iarc[i].s>0)
			height[u]=min(height[u],height[iarc[i].t]);
	height[u]++;
}
 
void initial(int vex)	{
	int i,j,t;
	qh=0;qt=0;
	memset(height,0,sizeof(height));
	height[1]=vex;
	memset(flow,0,sizeof(flow));
	memset(inQ,0,sizeof(inQ));
	for(i=star[1];i<star[2];i++)
	{
		if(iarc[i].v>0)
			{
				t=iarc[i].t;
				flow[1]-=iarc[i].v;
				flow[t]+=iarc[i].v;
				for(j=star[t];j<star[t+1]&&iarc[j].t!=1;j++)
				{;}
				iarc[i].s+=iarc[i].v;
				iarc[j].s-=iarc[i].v;
				if(t!=vex&&!inQ[t])
					{
						que[qt++]=t;
						qt%=QUERY;
						inQ[t]=1;
					}
			}
	}
}
 
int maxflow(int vex)	{
	int i;
	int s,t;
	initial(vex);
	while((qt-qh+QUERY)%QUERY)
	{
		s=que[qh];
		i=star[s];
		while(flow[s]>0)
		{
			if(i==star[s+1])
				{
					relabel(s);
					i=star[s];
				}
			else if((iarc[i].v-iarc[i].s)>0&&height[s]==height[iarc[i].t]+1)
				push(s,iarc+i,vex);
			else
				i++;
		}
		qh++;
		qh=qh%QUERY;
		inQ[s]=0;
	}
	return flow[vex];
}
 
int main(void)
{
	int i,j;
	int vex,arc;
	int ts,tt,tv;
	int bk1,bk2;
	FILE *fin,*fout;
	fin=stdin;
	fout=stdout;
	//fin=fopen("data.in","r");
	//fout=fopen("data.out","w+");
	while(fscanf(fin,"%d%d",&arc,&vex)!=EOF)
	{
		memset(star,0,sizeof(star));
		for(i=1;i<=arc;i++)
		{
			scanf("%d%d%d",&ts,&tt,&tv);
			for(j=2*i-1;j>1&&ts<iarc[j-1].s;j--)
				iarc[j]=iarc[j-1];
			iarc[j].s=ts;iarc[j].t=tt;iarc[j].v=tv;
			for(j=2*i;j>1&&tt<iarc[j-1].s;j--)
				iarc[j]=iarc[j-1];
			iarc[j].s=tt;iarc[j].t=ts;iarc[j].v=0;
			star[ts]++;
			star[tt]++;
		}
		bk1=0;
		star[0]=1;
		for(i=1;i<=vex+1;i++)
		{
			bk2=star[i];
			star[i]=star[i-1]+bk1;
			bk1=bk2;
		}
		for(i=1;i<=2*arc;i++)
			iarc[i].s=0;
		fprintf(fout,"%d\n",maxflow(vex));
	}
	return 0;
}