https://www.luogu.org/problem/show?pid=3381

題目描述

如題，給出一個網絡圖，以及其源點和匯點，每條邊已知其最大流量和單位流量費用，求出其網絡最大流和在最大流情況下的最小費用。

輸入輸出格式

輸入格式：

?

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

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

?

輸出格式：

?

一行，包含兩個整數，依次為最大流量和在最大流量情況下的最小費用。

?

輸入輸出樣例

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

說明

時空限制：1000ms,128M

（BYX：最后兩個點改成了1200ms）

數據規模：

對于30%的數據：N<=10，M<=10

對于70%的數據：N<=1000，M<=1000

對于100%的數據：N<=5000，M<=50000

樣例說明：

如圖，最優方案如下：

第一條流為4-->3，流量為20，費用為3*20=60。

第二條流為4-->2-->3，流量為20，費用為（2+1）*20=60。

第三條流為4-->2-->1-->3，流量為10，費用為（2+9+5）*10=160。

故最大流量為50，在此狀況下最小費用為60+60+160=280。

故輸出50 280。

?

反邊隨用隨加

只需要在spfa的時候記錄路徑最小流量

在給每條邊減流量的時候新建反邊即可

#include<cstdio> #include<queue> #define N 50010 using namespace std; queue<int>q; int n,m,tot; int src,dec; int to[N*2],from[N*2],nextt[N*2],front[N],cap[N*2],cost[N*2],dis[N],pre[N*2]; int minn[N]; bool v[N]; int sum_cost,sum_flow; void add(int u,int v,int f,int w) {to[++tot]=v;from[tot]=u;nextt[tot]=front[u];front[u]=tot;cap[tot]=f;cost[tot]=w; } bool spfa() {for(int i=1;i<=n;i++) dis[i]=0x7fffffff,minn[i]=0x7fffffff;q.push(src);v[src]=true;dis[src]=0;while(!q.empty()){int now=q.front();q.pop();v[now]=false;for(int i=front[now];i;i=nextt[i]){if(dis[to[i]]>dis[now]+cost[i]&&cap[i]>0){dis[to[i]]=dis[now]+cost[i];minn[to[i]]=min(minn[now],cap[i]);pre[to[i]]=i;if(!v[to[i]]){q.push(to[i]);v[to[i]]=true;}}}}return dis[dec]!=0x7fffffff; } int main() {scanf("%d%d%d%d",&n,&m,&src,&dec);int u,v,w,f;for(int i=1;i<=m;i++){scanf("%d%d%d%d",&u,&v,&w,&f);add(u,v,w,f);}while(spfa()){if(sum_cost+minn[dec]*dis[dec]>=0){sum_cost+=dis[dec]*minn[dec];sum_flow+=minn[dec];for(int i=pre[dec];i;i=pre[from[i]]) {cap[i]-=minn[dec];add(to[i],from[i],minn[dec],-cost[i]);}} else{sum_flow-=int(sum_cost/dis[dec]);break;}}printf("%d %d",sum_flow,sum_cost); }

?

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/7223663.html

總結

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

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