P3376 【模板】網絡最大流

題目描述

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

輸入輸出格式

輸入格式：

?

第一行包含四個正整數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。

/*一定要建邊權為0的反向邊別忘了dinic的三個優化：1、當前弧優化，訪問這個點的出邊時，從上一次訪問的下一條邊開始2、當增廣到某個點時，增廣過程中，已出去的流量==進來的，停止增廣；增廣完畢時，出去的流量<進來的流量，標記這個點，以后不再訪問此點3、分層時，找到匯點后即刻return，不要等到隊列為空*/ #include<iostream> #include<cstdio> #include<queue> #define maxn 10010 using namespace std; int n,m,ans,head[maxn],cur[maxn],f[maxn],lev[maxn],num=1,s,t; struct node{int to,pre,cap; }e[100010*2]; void Insert(int from,int to,int v){e[++num].to=to;e[num].cap=v;e[num].pre=head[from];head[from]=num; } bool bfs(int st){queue<int>q;q.push(st);for(int i=1;i<=n;i++)cur[i]=head[i],lev[i]=-1;lev[st]=0;while(!q.empty()){int now=q.front();q.pop();for(int i=head[now];i;i=e[i].pre){int to=e[i].to;if(lev[to]==-1&&e[i].cap>0){lev[to]=lev[now]+1;q.push(to);if(to==t)return 1;}}}return 0; } int dinic(int now,int flow){if(now==t)return flow;int rest=0,delta;for(int &i=cur[now];i;i=e[i].pre){int to=e[i].to;if(e[i].cap>0&&lev[to]==lev[now]+1){delta=dinic(to,min(flow-rest,e[i].cap));if(delta){e[i].cap-=delta;e[i^1].cap+=delta;rest+=delta;if(rest==flow)break;}}}if(rest!=flow)lev[now]=-1;return rest; } int main(){scanf("%d%d%d%d",&n,&m,&s,&t);int x,y,z;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);Insert(x,y,z);Insert(y,x,0);}while(bfs(s))ans+=dinic(s,0x7fffffff);printf("%d",ans); }

?

轉載于:https://www.cnblogs.com/thmyl/p/8055984.html

總結

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

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