# 图的最大流算法

1.网络流问题(NetWork Flow Problem):

The network flow problem considers a graph G with a set of sources S and sinks T and for which each edge has an assigned capacity (weight), and then asks to find the maximum flow that can be routed from S to T while respecting the given edge capacities.

2.三个基本的性质:

3.容量网络&流量网络&残留网络:

4.割&割集:

A set of edges of a graph which, if removed (or “cut”), disconnects the graph (i.e., forms a disconnected graph).

Given a weighted, undirected graph G=(V,E) and a graphical partition of V into two sets A and B, the cut of G with respect to A and B is defined as cut(A,B)=sum_(i in A,j in B)W(i,j),where W(i,j) denotes the weight for the edge connecting vertices i and j. The weight of the cut is the sum of weights of edges crossing the cut.

Ford-Fulkerson方法依赖于三种重要思想，这三个思想就是在上文中提到的：残留网络，增广路径和割。

Ford-Fulkerson方法是一种迭代的方法。开始时，对所有的u，v∈V有f(u,v)=0，即初始状态时流的值为0。在每次迭代中，可通过寻找一条“增广路径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直至增广路径都被找出来，根据最大流最小割定理，当不包含增广路径时，f是G中的一个最大流。在算法导论中给出的Ford-Fulkerson实现代码如下：

FORD_FULKERSON(G,s,t)
1   for each edge(u,v)∈E[G]
2        do f[u,v] <— 0
3            f[v,u] <— 0
4   while there exists a path p from s to t in the residual network Gf
5        do cf(p) <— min{ cf(u,v) : (u,v) is in p }
6        for each edge(u,v) in p
7             do f[u,v] <— f[u,v]+cf(p)  //对于在增广路径上的正向的边，加上增加的流
8                  f[v,u] <— -f[u,v]     //对于反向的边，根据反对称性求

int c[MAX][MAX];  //残留网络容量
int pre[MAX];  //保存增广路径上的点的前驱顶点
bool visit[MAX];
int Ford_Fulkerson(int src,int des,int n){   //src：源点 des：汇点 n：顶点个数
int i,_min,total=0;
while(true){
_min=(1<<30);
i=des;
while(i!=src){   //通过pre数组查找增广路径上的边，求出残留容量的最小值
if(_min>c[pre[i]][i])_min=c[pre[i]][i];
i=pre[i];
}
i=des;
while(i!=src){    //再次遍历，更新增广路径上边的流值
c[pre[i]][i]-=_min;
c[i][pre[i]]+=_min;
i=pre[i];
}
total+=_min;     //每次加上更新的值
}
}

Edmonds-Karp算法实际上就是采用广度优先搜索来实现对增广路径的p的计算，代码如下：

bool Edmonds_Karp(int src,int des,int n){
int v,i;
for(i=0;i<n;i++)visit[i]=false;
front=rear=0;     //初始化
que[rear++]=src;
visit[src]=true;
while(front!=rear){     //将源点进队后开始广搜的操作
v=que[front++];
//这里如果采用邻接表的链表实现会有更好的效率，但是要注意(u,v)或(v,u)有任何一条
//边存在于原网络流中，那么邻接表中既要包含(u,v)也要包含(v,u)
for(i=0;i<n;i++){
if(!visit[i]&&c[v][i]){  //只有残留容量大于0时才存在边
que[rear++]=i;
visit[i]=true;
pre[i]=v;
if(i==des)return true;   //如果已经到达汇点，说明存在增广路径返回true
}
}
}
return false;
}

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int ans[300],g[300][300],m,n,x,y,z;
bool vis[300];
bool bfs(int s,int e)
{
int now;
queue<int>que;
memset(ans,-1,sizeof ans);
memset(vis,0,sizeof vis);
ans[s]=s;
vis[s]=1;
que.push(s);
while(!que.empty())
{
now=que.front();
que.pop();
for (int i=1;i<=n;i++)
if (g[now][i]>0 && !vis[i])
{
vis[i]=1;
ans[i]=now;
if (i==e)
return true;
que.push(i);
}
}
return false;
}
int EdmondsKarp(int s,int e)
{
int flow=0;
while(bfs(s,e))
{
int dis=0x3f3f3f3f;
for (int i=e;i!=s;i=ans[i])
if (dis>g[ans[i]][i])
dis=g[ans[i]][i];
for (int i=e;i!=s;i=ans[i])
{
g[ans[i]][i]-=dis;
g[i][ans[i]]+=dis;
}
flow+=dis;
}
return flow;
}
main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(g,0,sizeof(g));
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
g[x][y]+=z;
}
printf("%d\n",EdmondsKarp(1,n));
}

}

poj1273 裸的最大流

Dinic 算法

Dinic算法的基本思路:

1、根据残量网络计算层次图。
2、在层次图中使用DFS进行增广直到不存在增广路
3、重复以上步骤直到无法增广

c++模板题

poj1273 裸的最大流

#include <cstdio>
#include <queue>
#include <cstring>
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
int dis[300],g[300][300],m,n,x,y,z;
int bfs(int s,int e)
{
int now;
queue<int>que;
memset(dis,-1,sizeof dis);
dis[s]=1;
que.push(s);
while(!que.empty())
{
now=que.front();
que.pop();
for (int i=1;i<=n;i++)
if (g[now][i]>0 && dis[i]<0)
{
dis[i]=dis[now]+1;
que.push(i);
}
}
if (dis[e]>0) return 1;
return 0;
}
int finds(int x,int low)
{
int a;
if (x==n) return low;
for (int i=1;i<=n;i++)
if (g[x][i]>0 && dis[x]+1==dis[i] && (a=finds(i,min(low,g[x][i]))))
{
g[x][i]-=a;
g[i][x]+=a;
return a;
}
return 0;
}
int Dinic(int s,int e)
{
int flow=0;
while(bfs(s,e))
{
while(x=finds(s,0x3f3f3f3f))
flow+=x;
}
return flow;
}
main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(g,0,sizeof(g));
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
g[x][y]+=z;
}
printf("%d\n",Dinic(1,n));
}
}


1. 对于多源多汇问题，只需要添加一个超源点和一个超汇点，将其转化为单源单汇问题即可，如下图。

1. 对于在顶点处有流量限制的问题，可以对源图进行扩展，既构建一个新的图，新的图的顶点数是源图的两倍，