网络流之最小费用最大流（dinic+SPFA 模板）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=5e3+5;
const int M=5e4+5;
const int inf=0x3f3f3f3f3f3f3f3f;
struct Edge{
int to,w,next,cost;//w 是容量，cost 是单位流量花费 
}edge[M*2];
int head[N],dis[N],vis[N],cur[N];
int n,m,s,t,cnt,min_cost=0;//min_cost 记录最小花费 
void add(int u,int v,int w,int cost){
edge[cnt]={v,w,head[u],cost};
head[u]=cnt++;
}
bool spfa(){
memset(vis,0,sizeof vis);
memset(dis,inf,sizeof dis);
queue<int> q;
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(edge[i].w && dis[u]+edge[i].cost<dis[v]){
dis[v]=dis[u]+edge[i].cost;
if(!vis[v]) vis[v]=1,q.push(v);
}
}
}//在开始 dfs 之前 vis 已经被初始化成 0 了 
if(dis[t]!=inf) return true;
return false;
}
int dfs(int u,int flow){
vis[u]=1;//标记走过的点，防止死循环 
if(u==t) return flow;
for(int i=cur[u];i!=-1;i=edge[i].next){
cur[u]=i;//当前弧优化 
int v=edge[i].to;
if(edge[i].w && dis[v]==dis[u]+edge[i].cost && !vis[v]){//dis[v]==dis[u]+edge[i].cost 跟着最短路走 
int tmp=dfs(v,min(flow,edge[i].w));
if(tmp){
edge[i].w-=tmp;
edge[i^1].w+=tmp;
min_cost+=tmp*edge[i].cost;//累加最小花费 
return tmp;
}
}
}
vis[u]=0;
return 0;
}
int dinic(){
int ans=0;
while(spfa()){//最短路分层 
memcpy(cur,head,sizeof head);// cur 初始化 
while(int tot=dfs(s,inf)) ans+=tot;//dfs(s,inf)为 0 时，就说明此时没有增广流 
}
return ans;
}
signed main(){
IOS
cin >> n >> m >> s >> t;
memset(head,-1,sizeof head);
for(int i=1;i<=m;i++){
int u,v,w,cost;
cin >> u >> v >> w >> cost;
add(u,v,w,cost);
add(v,u,0,-cost);
}
int flow=dinic();
cout << flow << " " << min_cost << endl;
return 0;
}

模板题：P3381 【模板】最小费用最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

原文地址：https://blog.csdn.net/2301_81488029/article/details/142384908

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！