G : 最大流问题

Description

给出一张网络有向图，源点及汇点，计算其最大流。 该网络中的顶点编号为1~N，发点和汇点在输入中指定。

Input

第一行给出四个整数N(1 <= N <= 200), M(N <= M <= 5000),S,T，分别表示节点数量、有向边数量、源点序号、汇点序号。

接下来M行每行包括三个正整数ui，vi，wi，表示第 i条有向边从 ui出发，到达 vi，边权为 wi。0<wi<=10000

Output

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

Sample Input

6 9 4 2
1 3 10
2 1 20
2 3 20
4 3 10
4 5 30
5 2 20
4 6 20
5 6 10
6 2 30

Sample Output

50

Hint

问题表述：给定一幅图（n个结点，m条边），每一条边有一个容量，现在需要将一些物品从结点s（称为源点）运送到结点t（称为汇点），可以从其他结点中转，求最大的运送量。

在介绍最大流问题的解决方法之前，先介绍几个概念.

网络：网络是一个有向带权图，包含一个源点和一个汇点，没有反向平行边。

网络流：网络流即网上的流，是定义在网络边集E上的一个非负函数flow={flow（u，v）}, flow（u,v）是边上的流量。

可行流：满足以下两个性质的网络流flow称为可行流。

容量约束：每条边的实际流量不能超过改变的最大流量。

流量守恒：除了源点s和汇点t之外，所有内部节点流入量等于流出量。

源点s：源点主要是流出，但也有可能流入。

源点的净输出值=流出量之和-流入量之和。

汇点t：汇点主要是流入，但也有可能流出。

汇点的净输入值=流入量之和-流出量之和。

对于一个网络可行流flow，净输出等于净输入，这仍然是流量守恒。

网络最大流：在满足容量约束和流量守恒的前提下，在流网络中找到一个净输出最大的网络流。

反向弧：若从u到v的边的容量为c ，这条边上有流量 f 流过（称为正向弧），则相当于v到u有一条容量为0的边，其流量为- f ，这条边就是反向弧。反向弧的作用主要是用于寻找增广路。

反向弧的意义：反向弧的作用是起到有更优决策的时候会使当前选择的弧会自动放弃。反向弧有流量的原因是因为如果刚刚选择了正向弧，下一次如果存在更优策略使这f的流量流入汇点，就可以选择反向弧，将流量 f 撤销。

残余网络：计算出图中的每条边上容量与流量之差（称为残余容量），即可得到残余网络。注意由于反向边的存在，残余网络中的边数可能到达原图中边数的两倍。

增广路径：残余网络中任何一条从s到t的有向道路都对应一条原图中的增广路径 —— 只要求出该道路中所有残量的最小值d ，把对应的所有边上的流量增加d 即可，这个过程称为增广。

最大流定理：如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。

二、AC代码

#include <iostream>
#include <cstring>
#include<queue>

#include<vector>
using namespace std;
int n,m;
const int maxn=1005;
int g[maxn][maxn];//容量
int f[maxn][maxn];//流量
int vis[maxn];
int pre[maxn];//前驱数组
const int INF =1111111;

int bfs(int s,int t)
{
    
    memset(pre,-1,sizeof(pre));//初始化数组
    memset(vis,0,sizeof(vis));

    queue<int > q;
    vis[s]=1;//记录时间
    q.push(s);//加入队列
   // cout<<s<<t<<endl;

    while(!q.empty())
    {
    
        int now=q.front();
        q.pop();

        for(int i=1;i<=n;i++)
        {
    
            if(!vis[i]&&g[now][i])
            {
    

                vis[i]=1;
                pre[i]=now;
                if(i==t)return 1;//到终点了就退出
                q.push(i);


            }
        }
    }
    return 0;
}

 int u,v;
int EK(int s,int t)
{
    
    int maxflow=0;
   
    while(bfs(s,t))//bfs找路径
    {
    
        int d=INF;
        v=t;
        while(v!=s)//利用前驱回置到最初s，并求出最小流，满足容量约束
        {
    
            //获取前驱
            u=pre[v];


            //求路径上的最小容量
            if(d>g[u][v])d=g[u][v];

            //向前迭代
            v=u;
        }

        maxflow+=d;//最大流=+所有路径上的最小容量
       // cout<<d<<endl;
        v=t;
        while(v!=s)
        {
    
            //获取前驱
            u=pre[v];

            //求增广路径
            g[u][v]-=d;
            g[v][u]+=d;//满足流量约束，输入输出流相等
            if(f[v][u]>0)f[v][u]=-d;
            else f[u][v]+=d;

             //向前迭代
            v=u;
        }

    }
    //cout<<maxflow<<endl;;
    return maxflow;
}
int main()
{
    
    int s,t;
    while(cin>>n>>m>>s>>t)
    {
    
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(int i=0;i<m;i++)
        {
    
            int u,v,w;
            cin>>u>>v>>w;
            g[u][v]+=w;
        }
        cout<<EK(s,t)<<endl;

    }
    return 0;
}