# 求最大网络流（最小割）总结

一个有向图，每条边都有最大可能的数据传输量c，要求一个点到某个点一次能传输的最大数据量，即为求最大网络流，每条边实际的数据传输量称为流量。

Ford-fulkerson算法

1. 读入所有有向边，并且加入流量为0的反向边
2. DFS查找所有点u的未被遍历的边(u,v)
3. 如果满足这条边流量大于0，更新这条边以及它的反向边的流量（同时会DFS遍历v点）
4. 重复2操作，直到所有点被遍历完成

Dinic算法

1. BFS求源点到所有点的距离
2. DFS 遍历所有边(u,v)
3. 如果dis[v]==dis[u]+1且边的长度大于0，那么更新这条边以及它的反向边的流量（同时DFS遍历了v点）

1. 重复2操作，直到没有符合条件的边为止

算法复杂度：O(n^2*m)。（最坏情况，平均情况大大优于FF算法）

定理1：如果f是网络中的一个流，那么f的流为割的正向边与逆向边容量之差

定理二：如果f是一个流，CUT (S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割。

推论：f的流量<=此流的割的容量

POJ 1273 Drainage Ditches

Description

Every time itrains on Farmer John's fields, a pond forms over Bessie's favorite cloverpatch. This means that the clover is covered by water for awhile and takesquite a long time to regrow. Thus, Farmer John has built a set of drainageditches so that Bessie's clover patch is never covered in water. Instead, thewater is drained to a nearby stream. Being an ace engineer, Farmer John hasalso installed regulators at the beginning of each ditch, so he can control atwhat rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transportper minute but also the exact layout of the ditches, which feed out of the pondand into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can betransported out of the pond and into the stream. For any given ditch, waterflows in only one direction, but there might be a way that water can flow in acircle.

Input

The input includesseveral cases. For each case, the first line contains twospace-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200).N is the number of ditches that Farmer John has dug. M is the number of intersectionspoints for those ditches. Intersection 1 is the pond. Intersection point M isthe stream. Each of the following N lines contains three integers, Si, Ei, andCi. Si and Ei (1 <= Si, Ei <= M) designate the intersections betweenwhich this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0<= Ci <= 10,000,000) is the maximum rate at which water will flow throughthe ditch.

Output

For each case,output a single integer, the maximum rate at which water may emptied from thepond.

Sample Input

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

Sample Output

50

Ford-Fulkerson算法

#include
#include
#include
using namespace std;
const int MAX=600;
int first[MAX],nxt[MAX],go[MAX],flow[MAX],arcnum=1;
int vis[MAX];
nxt[++arcnum]=first[a];
first[a]=arcnum;
go[arcnum]=b;
flow[arcnum]=c;//记录该边容量
}

int Dfs(int u,int t,int minc){//起点u，终点t，整条路径中流量最小为minc
if(u==t) return minc;
vis[u]=1;
for(int p=first[u];p!=0;p=nxt[p]){
int v=go[p];
if(!vis[v]&&flow[p]>0){
int f=Dfs(v,t,min(minc,flow[p]));
if(f>0){
flow[p]-=f;//正向边减去算出的流量
flow[p^1]+=f;//逆向边加上算出的流量
/* n为任意偶自然数，那么n^1=n+1;(n+1)^1=n    */
return f;
}
}
}
return 0;//如果都不符合条件，返回0
}

int MaxFlow(int s,int t){
int ans=0;
while(1){
memset(vis,0,sizeof(vis));
int f=Dfs(s,t,99999999);
if(f<=0) return ans;
ans+=f;
}
}

int main()
{
//   freopen("in.txt","r",stdin);
int n,m,a,b,c;
while(scanf("%d%d",&m,&n)!=EOF){
memset(first,0,sizeof(first));
memset(flow,0,sizeof(flow));
arcnum=1;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
}
printf("%d\n",MaxFlow(1,n));
}

return 0;
} Dinic算法

#include
#include
#include
#include
using namespace std;
const int MAX=600;
const int INF=99999999;
int first[MAX],go[MAX],nxt[MAX],flow[MAX],arcnum=1;
int que[MAX*MAX],dis[MAX],top,rear,current[MAX],vis[MAX];
int n,m,a,b,c;
nxt[++arcnum]=first[a];
first[a]=arcnum;
go[arcnum]=b;
flow[arcnum]=c;
}

int DFS(int u,int t,int minc){
//   printf("dfs %d %d start\n",u,t);
if(u==t) return minc;
for(int p=current[u];p!=0;p=nxt[p]){

current[u]=p;
int v=go[p];
//       printf("%d: %d->%d\n",p,u,v);
if(dis[v]==dis[u]+1&&flow[p]>0){//边一定要存在
int f=DFS(v,t,min(minc,flow[p]));
if(f){
flow[p]-=f;
flow[p^1]+=f;
return f;
}
}
}
return 0;
}

int BFS(int s,int t){//BFS优化
for(int i=1;i<=MAX;i++)
dis[i]=INF;
top=rear=0;
que[rear++]=s;
dis[s]=1;
do{
int u=que[top++],v;
for(int p=first[u];p!=0;p=nxt[p]){
v=go[p];
if(flow[p]>0&&dis[v]==INF){//边存在且点未被更新时才更新
dis[v]=dis[u]+1;
que[rear++]=v;
}
}
}while(top!=rear);
return dis[t]int MaxFlow(int s,int t){//Dinic算法
int ans=0,f;

while(BFS(s,t)){
for(int i=1;i<=n;i++)
current[i]=first[i];//每次BFS后都要重置current数组
while(f=DFS(s,t,INF))
ans+=f;
}

return ans;
}

int main(){
freopen("in.txt","r",stdin);
while(scanf("%d%d",&m,&n)!=EOF){
memset(first,0,sizeof(first));
memset(flow,0,sizeof(flow));
arcnum=1;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
}
/*       for(int i=1;i<=n;i++){
printf("%d %d\n",i,first[i]);
}
printf("node end\n");
for(int i=1;i<=2*m;i++){
printf("%d %d %d\n",i,go[i],nxt[i]);
}
printf("edge end\n");*/
printf("%d\n",MaxFlow(1,n));
}

return 0;
} 