最小费用最大流模板

#include "stdio.h" //poj 2135 最小费用最大流模板
#include "string.h"
#include <queue>
using namespace std;

#define N 1005
#define INF 0x3fffffff

struct node 
{
	int u,v;
	int w,k;
	int next;
}edge[4*N*10];  //题目中边的条数是N的十倍，每一条边建四次！

int n,m,idx,ans;
int head[N],dis[N],route[N];
bool mark[N];

void init(); //初始化部分变量
void EK(int start,int end);
int SPFA(int start,int end);
void adde(int u,int v,int w,int k);
void addedge(int u,int v,int w,int k);


int main()
{
	int i;
	int u,v,w;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		init();
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&u,&v,&w);   //对每一条边建两次，一正一反
			adde(u,v,w,1);
			adde(v,u,w,1);
		}
		int start = 0;
		adde(start,1,0,2);  //为起点添两条边，单位流量费用为0
		int end = n+1;
		adde(n,end,0,2);   //为终点添两条边,单位流量费用为0
		while( SPFA(start,end) )
			EK(start,end);
		printf("%d
",ans);
	}
	return 0;
}

void init()
{
	ans = 0;  //结果初始化
	idx = 0;  
	memset(head,-1,sizeof(head));  //
}

void adde(int u,int v,int w,int k)  //对其中的一条再加上一条流量为0的回路
{
	addedge(u,v,w,k);
	addedge(v,u,-w,0);
}

void addedge(int u,int v,int w,int k)  //邻接表建边
{
	edge[idx].u = u;
	edge[idx].v = v;
	edge[idx].w = w;
	edge[idx].k = k;
	edge[idx].next = head[u];
	head[u] = idx;
	idx++;
}

int SPFA(int start,int end)  //找一条存在流量的最小费用流(存在流量就行)
{
	int i;
	memset(mark,false,sizeof(mark));  //初始化标记数组mark[];
	memset(route,-1,sizeof(route));   //ruote[]记录流量路径(存下一条边的下标)
	for(i=start;i<=end;i++)		dis[i] = INF;
	dis[start] = 0;
	queue<int> q;
	q.push(start);
	mark[start] = true;
	int x,y;
	while(!q.empty())
	{
		x = q.front();
		for(i=head[x];i!=-1;i=edge[i].next)
		{
			y = edge[i].v;
			if(edge[i].k && dis[y] > dis[x] + edge[i].w)
			{
				dis[y] = dis[x] + edge[i].w;
				route[y] = i;   //route[]里面存的为边的下标
				if(mark[y] == false)
				{ 
					mark[y] = true;
					q.push(y);
				}
			}
		}
		q.pop();
		mark[x] = false;  //对出队列的点的标记还原
	}
	if(dis[end] == INF) return 0;
	return 1;
}

void EK(int start,int end)
{
	int x,y;
	y = route[end];
	//对于一般的最小费用最大流，需遍历一遍route[],求出最小费用路线上能流过的最大流量k(此题恰好为1，故此步省略！)
	while(y!=-1)
	{
		x = y^1;  //很特别的处理;
		edge[y].k--;  //对流量进行处理(正减反加)
		edge[x].k++;
		ans += edge[y].w;
		y = route[edge[y].u]; //通过route[]访问路径上的下一个节点
	}
}