网络流之——最大流

??? 最大流算法是网络流中基础的算法，解决的方法有很多，比如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，容量为该客户购买量。这样，就转化为简单的网络流。

?

?

?

?