POJ2135最小费用最大流

第一次写费用流，仔细想过后也不过是这么回事。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005,M=10020,INF=0x3f3f3f3f;
int n,m;
struct G{
	int base[N],vec[4*M],pre[4*M],cost[4*M],flow[4*M],tot;
	int S,T;
	int mincost,maxflow;
	int dis[N],que[N];
	int pv[N],pe[N];
	bool vis[N];
	void link(int x,int y,int z,int f)
	{
		vec[++tot]=y;  pre[tot]=base[x];  base[x]=tot; cost[tot]=z; flow[tot]=f;
		vec[++tot]=x;  pre[tot]=base[y];  base[y]=tot; cost[tot]=-z; flow[tot]=0;
	}
	void build()
	{
		memset(base,0,sizeof(base));
		tot=1;
		int x,y,z;
		scanf("%d%d",&n,&m);
		for (int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			link(x,y,z,1);
			link(y,x,z,1);
		}
		S=0;  T=n+1;
		link(S,1,0,2);
		link(n,T,0,2);
	}
	bool spfa()
	{
		memset(vis,0,sizeof(vis));
		memset(pv,-1,sizeof(pv));
		memset(dis,0x3f3f3f3f,sizeof(dis));
		int head=0,tail=1;
		que[tail]=S;  vis[S]=1;  dis[S]=0;
		while(head!=tail)
		{
			head++;
			head%=N;
			int u=que[head];
			vis[u]=0;

			for (int now=base[u];now;now=pre[now])
			if (flow[now]>0)
			{
				int v=vec[now];
				if (dis[u]+cost[now]<dis[v])
				{
					dis[v]=dis[u]+cost[now];
					pv[v]=u;
					pe[v]=now;
					if (!vis[v])
					{
						vis[v]=1;
						tail++;
						tail%=N;
						que[tail]=v;
					}
				}
			}
		}
		if (dis[T]!=INF) return 1;else return 0;
	}
	void work()
	{
		mincost=0;
		maxflow=0;
		while(spfa())
		{
			int mxf=INF;
			mincost+=dis[T];
			for (int v=T;v!=S;v=pv[v])
				mxf=min(mxf,flow[pe[v]]);
			maxflow+=mxf;
			for (int v=T;v!=S;v=pv[v])
				flow[pe[v]]-=mxf,flow[pe[v]^1]+=mxf;
		}
	}
}g;
int main()
{
	g.build();
	g.work();
	printf("%d\n",g.mincost);
}