网络源之——最大流
最大流算法是网络流中基础的算法，解决的方法有很多，比如EK,Dinic,sap等等，在这里介绍一下EK算法。
从源点s开始广度优先寻找一条到t的路径，计算出这条路径的最大流量（短板效应）l，回溯，将这条路径的每条边的最大流量减去l，然后添加反向边，容量为l，网络流的最大流max+=l。当找不到从s到t的一条路径时退出，最大流量即为max。
EK模板：
其实，当已知一个网络，求最大流就非常简单，直接套用模板就行，但往往难点在建图，如何将题目描述转化为一个单源单汇的网络，下面列举几个题目： POJ1459 题目大意：有n个发电站，m个变压器，c个消费者，发电站不消耗电能，消费者不产生电能，变压器既不产生电能也不消耗电能。每个发电站都有最大的发电量，消费者也有最大的消耗量，每两个点之间的线路也有最大容量。现在要求出这个网络的最大流量（显然，在整个网络中，产生电量=消耗电量）。 分析：显然这是一个多源多汇的网络模型，可以做如下转化：增加一个超级源点s，它跟每个发电站连一条线，容量为发电站的最大发电量，增加一个超级汇点t，每个消费者跟它连一条线，容量为消费者的最大消费量。这样，问题就转化为求这样单源单汇的简单网络流。 POJ1149 题目大意：一个养猪场有n个猪房，每个猪房可以装无限多的猪，每个顾客都有特定的猪房钥匙和购买量，每个顾客买完后重新锁上打开的猪房，但锁上之前可以将某猪房的猪分一些给另外一些猪房（即打开的猪房之间可以相互调整数量），问最多能卖出多少头猪。 分析：可以把顾客作为结点，增加源点s和汇点t，如果该客户是第一个拥有猪房钥匙的人，从源点连接一条边到该客户；如果不是第一人，那么从前一个拥有该猪房钥匙的客户连一条边到该客户，容量为无穷；从每个客户连一条边到t，容量为该客户购买量。这样，就转化为简单的网络流。#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;
}