网络最大流FF算法

题目描述

如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。

输入输出格式

输入格式：

第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）

输出格式：

一行，包含一个正整数，即为该网络的最大流。

输入输出样例

输入样例#1：

输出样例#1：

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，M<=25

对于70%的数据：N<=200，M<=1000

对于100%的数据：N<=10000，M<=100000

样例说明：

题目中存在3条路径：

4-->2-->3，该路线可通过20的流量

4-->3，可通过20的流量

4-->2-->1-->3，可通过10的流量（边4-->2之前已经耗费了20的流量）

故流量总计20+20+10=50。输出50。

求网络最大流的算法还是很多的，这里讲一下最简单的FF算法。

还是利用增广路，找到一条从源点到汇点的任意路径，所有边上的最小值delta如果不是0，

那么总流量就可以增加delta，在将路径上的边的容量减去delta，这就是一条增广路。

易知，如果找不出增广路了，那么此时的流量就是最大了。

但是，就这样还不行，如果“走错了”怎么办？

现在引进反向弧，反向弧可以解决这个问题。其他的博客上很多说反向弧可以让流量后悔，

这个比喻很生动，但用我自己的话来说，反向弧因为是同原边反向的，两者中一者减去delta时，

将另一者加上delta，那么之后找增广路时，走反向弧相当于原边少走，非常巧妙。

算法大概是将完了，代码应该还好打的。

#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define INF 2147483647
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct edge{
    int next,to,head,b;
}f[440000];
long long ans;
int tot=0,n,m,s,t;
bool mark[400000]={0},flag;
void add(int u,int v,int w){
    f[tot].next=f[u].head;f[u].head=tot;f[tot].to=v;f[tot].b=w;tot++;
}
int dfs(int x,int flow){//dfs求任意路径
    if(x==t){
        ans+=flow;
        flag=1;
        return flow;
    }
    mark[x]=1;
    for(int i=f[x].head;i!=-1;i=f[i].next){
        int x1=f[i].to;
        if(mark[x1]||f[i].b==0) continue;
        int delta=dfs(x1,min(flow,f[i].b));
        if(flag){
            f[i].b-=delta;
            f[i^1].b+=delta;
            return delta;
        }
    }
    return 0;
}
void FF(){//有增广路就增广
    memset(mark,0,sizeof(mark));
    flag=0;
    dfs(s,INF);
    while(flag){
        memset(mark,0,sizeof(mark));
        flag=0; 
        dfs(s,INF);
    }
}
int main(){
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=n;++i) f[i].head=-1;
    while(m--){
        int x,y,w;x=read();y=read();w=read();
        add(x,y,w);add(y,x,0);
    }
    FF();
    printf("%lld",ans);
    return 0;
}

注意，这种dfs的形式也是我自己很少打的，求任意一条路径，

先dfs到汇点，再做一个标记flag，回来时有标记就更新。