題目描述

如題，給出一個網絡圖，以及其源點和匯點，求出其網絡最大流。

輸入輸出格式

輸入格式：
第一行包含四個正整數N、M、S、T，分別表示點的個數、有向邊的個數、源點序號、匯點序號。

接下來M行每行包含三個正整數ui、vi、wi，表示第i條有向邊從ui出發，到達vi，邊權為wi（即該邊最大流量為wi）

輸出格式：
一行，包含一個正整數，即為該網絡的最大流。

輸入輸出樣例

輸入樣例#1：
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
輸出樣例#1：
50
說明

時空限制：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。

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<queue> using namespace std;int ls[100001],dis[100001]; int n,m,s,t,cnt,ans,x,y,w;queue<int> q; struct edge {int y,w,op,next; }a[500000];void add(int x,int y,int w) {a[++cnt]=(edge){y,w,cnt+1,ls[x]}; ls[x]=cnt;a[++cnt]=(edge){x,0,cnt-1,ls[y]};ls[y]=cnt; }bool bfs() {while (!q.empty()) q.pop();for (int i=1;i<=n;i++) dis[i]=2147483647; dis[s]=0; q.push(s);while (!q.empty()) {int x=q.front();q.pop();for (int i=ls[x];i>0;i=a[i].next){int y=a[i].y;if ((a[i].w)&&(dis[y]>dis[x]+1)){dis[y]=dis[x]+1;if (y==t) return 1;q.push(y);}}}return 0; }int dfs(int x,int q) {if (x==t) return q;int sum=0;for (int i=ls[x];i>0;i=a[i].next){int y=a[i].y;if ((a[i].w)&&(dis[y]==dis[x]+1)) {int f=dfs(y,min(a[i].w,q-sum)); if (!f) dis[y]=-1;a[i].w-=f; a[a[i].op].w+=f;sum+=f;if (sum==q) break;}}return sum; }int dinic() {int ans=0;while (bfs()) ans+=dfs(s,2147483647); return ans; }int main() {scanf("%d%d%d%d",&n,&m,&s,&t);for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&w);add(x,y,w);}ans=dinic();printf("%d",ans); }

轉載于:https://www.cnblogs.com/YYC-0304/p/11094944.html

總結

以上是生活随笔為你收集整理的【模板】网络最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。