傳送門 Luogu P3376 【模板】網(wǎng)絡(luò)最大流
題目描述
如題撩鹿，給出一個(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)序號赔桌、匯點(diǎn)序號供炎。
接下來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ī)模
對于30%的數(shù)據(jù)：N<=10，M<=25
對于70%的數(shù)據(jù)：N<=200聋袋，M<=1000
對于100%的數(shù)據(jù)：N<=10000队伟，M<=100000
樣例說明
題目中存在3條路徑：
4-->2-->3，該路線可通過20的流量
4-->3幽勒，可通過20的流量
4-->2-->1-->3嗜侮，可通過10的流量（邊4-->2之前已經(jīng)耗費(fèi)了20的流量）
故流量總計(jì)20+20+10=50。輸出50啥容。
算法詳解
首先是網(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).
對于每條邊(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.
對于每條邊(u,v),有一個(gè)流量f(u,v).
一個(gè)簡單的例子.網(wǎng)絡(luò)可以被想象成一些輸水的管道.括號內(nèi)右邊的數(shù)字表示管道的容量c,左邊的數(shù)字表示這條管道的當(dāng)前流量f.
網(wǎng)絡(luò)流的三個(gè)性質(zhì)：
1遥昧、容量限制: f[u,v]<=c[u,v]
2覆醇、反對稱性：f[u,v] = - f[v,u]
3、流量平衡: 對于不是源點(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)
通俗地講：就是對于某一條邊（也稱宦湮纭），還能再有多少流量經(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;//邊里存儲的分別是連接點(diǎn)、容量猫妙、反向邊的編號
};
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});
//對于一條邊瓷翻，它的反向邊的編號就是它所連向的點(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;
}
