Nephren Ruq Insania

題目描述

如題，給出一個(gè)網(wǎng)絡(luò)圖，以及其源點(diǎn)和匯點(diǎn)，求出其網(wǎng)絡(luò)最大流。

輸入輸出格式

輸入格式
第一行包含四個(gè)正整數(shù)N、M、S、T，分別表示點(diǎn)的個(gè)數(shù)、有向邊的個(gè)數(shù)、源點(diǎn)序號(hào)、匯點(diǎn)序號(hào)。
接下來M行每行包含三個(gè)正整數(shù)ui、vi、wi，表示第i條有向邊從ui出發(fā)，到達(dá)vi，邊權(quán)為wi（即該邊最大流量為wi）

輸出格式
一行，包含一個(gè)正整數(shù)，即為該網(wǎng)絡(luò)的最大流。

輸入輸出樣例

輸入樣例#1

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

輸出樣例#1

50

說明

數(shù)據(jù)規(guī)模
對(duì)于30%的數(shù)據(jù)：N<=10，M<=25
對(duì)于70%的數(shù)據(jù)：N<=200，M<=1000
對(duì)于100%的數(shù)據(jù)：N<=10000，M<=100000

樣例說明

圖源自洛谷

算法詳解

首先是網(wǎng)絡(luò)流中的一些定義：

V表示整個(gè)圖中的所有結(jié)點(diǎn)的集合.
E表示整個(gè)圖中所有邊的集合.
G = (V,E) ,表示整個(gè)圖.
s表示網(wǎng)絡(luò)的源點(diǎn),t表示網(wǎng)絡(luò)的匯點(diǎn).
對(duì)于每條邊(u,v),有一個(gè)容量c(u,v) (c(u,v)>=0)，如果c(u,v)=0，則表示(u,v)不存在在網(wǎng)絡(luò)中。相反，如果原網(wǎng)絡(luò)中不存在邊(u,v)，則令c(u,v)=0.
對(duì)于每條邊(u,v),有一個(gè)流量f(u,v).

一個(gè)簡(jiǎn)單的例子.網(wǎng)絡(luò)可以被想象成一些輸水的管道.括號(hào)內(nèi)右邊的數(shù)字表示管道的容量c,左邊的數(shù)字表示這條管道的當(dāng)前流量f.
網(wǎng)絡(luò)流的三個(gè)性質(zhì)：

1、容量限制: f[u,v]<=c[u,v]
2、反對(duì)稱性：f[u,v] = - f[v,u]
3、流量平衡: 對(duì)于不是源點(diǎn)也不是匯點(diǎn)的任意結(jié)點(diǎn),流入該結(jié)點(diǎn)的流量和等于流出該結(jié)點(diǎn)的流量和。

只要滿足這三個(gè)性質(zhì),就是一個(gè)合法的網(wǎng)絡(luò)流.
最大流問題，就是求在滿足網(wǎng)絡(luò)流性質(zhì)的情況下，源點(diǎn) s 到匯點(diǎn) t 的最大流量。
求一個(gè)網(wǎng)絡(luò)流的最大流有很多算法 這里首先介紹 增廣路算法（EK）
學(xué)習(xí)算法之前首先看了解這個(gè)算法中涉及到的幾個(gè)圖中的定義：

• 殘量網(wǎng)絡(luò)
  為了更方便算法的實(shí)現(xiàn)，一般根據(jù)原網(wǎng)絡(luò)定義一個(gè)殘量網(wǎng)絡(luò)。其中r(u,v)為殘量網(wǎng)絡(luò)的容量。
  r(u,v) = c(u,v) – f(u,v)
  通俗地講：就是對(duì)于某一條邊（也稱?。€能再有多少流量經(jīng)過。
• 增廣路
  在殘量網(wǎng)絡(luò)中的一條從s通往t的路徑，其中任意一條弧(u,v)，都有r[u,v]>0。
• 增廣路算法
  每次用DFS找一條最短的增廣路徑，然后沿著這條路徑修改流量值（實(shí)際修改的是殘量網(wǎng)絡(luò)的邊權(quán)）。當(dāng)沒有增廣路時(shí)，算法停止，此時(shí)的流就是最大流。

具體解釋看下面的代碼注釋吧

C++模板代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define rr register
using namespace std;

const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
int n,m,s,t,ans;
int vis[maxn];
struct edge{
    int to,c,rev;//邊里存儲(chǔ)的分別是連接點(diǎn)、容量、反向邊的編號(hào)
};
vector<edge>a[maxn];

inline int read(){//珂朵莉版快讀~~
    int chtholly=0,willem=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')willem=-1;c=getchar();}
    while(c<='9' && c>='0'){chtholly=chtholly*10+(int)(c-'0');c=getchar();}
    return chtholly*willem;
}

inline void add(int x,int y,int z){
    int S1=a[y].size(),S2=a[x].size();
    a[x].push_back((edge){y,z,S1});
    //對(duì)于一條邊，它的反向邊的編號(hào)就是它所連向的點(diǎn)此時(shí)所擁有的邊的個(gè)數(shù)+1
    //但vector里數(shù)組下標(biāo)都是0開始的，所以直接是a[x].size()就好了
    a[y].push_back((edge){x,0,S2});
}

inline int dfs(int x,int y,int now){
    if(x==y)return now;
    vis[x]=1;
    int S=a[x].size();
    for(rr int i=0;i<S;++i){
        int v=a[x][i].to,f=a[x][i].c,re=a[x][i].rev;
        if(!vis[v] && f>0){
            int tmp=dfs(v,y,min(f,now));//從子節(jié)點(diǎn)開始找增廣路
            if(tmp>0){//如果存在增廣路
                a[x][i].c-=tmp;//容量減去增加的流量就相當(dāng)于流量加上這么多
                a[v][re].c+=tmp;//正向邊流量增加相當(dāng)于反向邊流量減少
                return tmp;
            }
        }
    }
    return 0;
}

inline int max_flow(int x,int y){
    int flow=0,f=0;
    do{
        flow+=f;
        memset(vis,0,sizeof(vis));
        f=dfs(x,y,inf);
        //尋找增廣路，因?yàn)樵趯ふ疫^程中要取此時(shí)的流量與該路徑的容量的min值，故流量初始化為極大值
    }while(f!=0);//當(dāng)存在增廣路的時(shí)候就繼續(xù)找
    return flow;
}

int main(){
    n=read(),m=read(),s=read(),t=read();
    memset(a,0,sizeof(a));
    for(rr int i=1;i<=m;++i){
        int x=read(),y=read(),z=read();
        add(x,y,z);
    }
    ans=max_flow(s,t);
    printf("%d\n",ans);
    return 0;
}