网络流之——最大流

    最大流算法是网络流中基础的算法，解决的方法有很多，比如EK,Dinic,sap等等，在这里介绍一下EK算法。

    从源点s开始广度优先寻找一条到t的路径，计算出这条路径的最大流量（短板效应）l，回溯，将这条路径的每条边的最大流量减去l，然后添加反向边，容量为l，网络流的最大流max+=l。当找不到从s到t的一条路径时退出，最大流量即为max。

    EK模板：

#include <iostream>
#include <queue>
using namespace std;
const int N = 202;
const int INF = 0x7fffffff;
queue<int> q;
int n,m;		//m为标号(从1到m)，n为边数
int start,end;

int map[N][N];
int path[N];		//结点的前驱结点
int flow[N];		//标记从源点到当前节点实际还剩多少流量可用

int bfs()
{
	int i,t;
	while(!q.empty()) q.pop();
	memset(path,-1,sizeof(path));
	path[start] = 0, flow[start] = INF;			//初始化工作
	q.push(start);
	while(!q.empty())
	{
		t = q.front();
		q.pop();
		if(t == end) break;						//队列非空&&结点end未被访问
		for(i = 1; i <= m; i++)					//对t发出的每一条边(t,i),如果i未访问
		{
			if(i!=start && path[i]==-1 && map[t][i])
			{
				flow[i] = flow[t] < map[t][i] ? flow[t] : map[t][i];	//弧(t,i)可改进
				q.push(i);
				path[i] = t;
			}
		}
	}
	if(path[end] == -1)
		return -1;
	return flow[end];			//一次遍历之后的流量增量(剩余多少流量)
}

int Edmonds_Karp()
{
	int max_flow = 0;
	int step,now,pre;
	while((step=bfs())!=-1)				//找不到路径时退出
	{
		max_flow += step;
		now = end;
		while(now != start)
		{
			pre = path[now];
			map[pre][now] -= step;		//更新正向边的实际容量(涉及反向边和残余图，证明复杂，不去深究)
			map[now][pre] += step;		//添加反向边
			now = pre;
		}
	}
	return max_flow;
}

int main()
{
	int i,a,b,cost;
	while(scanf("%d %d",&n,&m) != EOF)
	{
		memset(map,0,sizeof(map));
		for(i = 0; i < n; i++)
		{
			scanf("%d %d %d",&a,&b,&cost);
			map[a][b] += cost;				//输入可能出现相同的边
		}
		start = 1, end = m;
		printf("%d\n",Edmonds_Karp());
	}
	return 0;
}

 其实，当已知一个网络，求最大流就非常简单，直接套用模板就行，但往往难点在建图，如何将题目描述转化为一个单源单汇的网络，下面列举几个题目：

POJ1459

题目大意：有n个发电站，m个变压器，c个消费者，发电站不消耗电能，消费者不产生电能，变压器既不产生电能也不消耗电能。每个发电站都有最大的发电量，消费者也有最大的消耗量，每两个点之间的线路也有最大容量。现在要求出这个网络的最大流量（显然，在整个网络中，产生电量=消耗电量）。

分析：显然这是一个多源多汇的网络模型，可以做如下转化：增加一个超级源点s，它跟每个发电站连一条线，容量为发电站的最大发电量，增加一个超级汇点t，每个消费者跟它连一条线，容量为消费者的最大消费量。这样，问题就转化为求这样单源单汇的简单网络流。

POJ1149

题目大意：一个养猪场有n个猪房，每个猪房可以装无限多的猪，每个顾客都有特定的猪房钥匙和购买量，每个顾客买完后重新锁上打开的猪房，但锁上之前可以将某猪房的猪分一些给另外一些猪房（即打开的猪房之间可以相互调整数量），问最多能卖出多少头猪。

分析：可以把顾客作为结点，增加源点s和汇点t，如果该客户是第一个拥有猪房钥匙的人，从源点连接一条边到该客户；如果不是第一人，那么从前一个拥有该猪房钥匙的客户连一条边到该客户，容量为无穷；从每个客户连一条边到t，容量为该客户购买量。这样，就转化为简单的网络流。