364 网络流 费用流 EK 算法

打印 上一主题 下一主题

主题 928|帖子 928|积分 2784

视频链接:https://www.bilibili.com/video/BV1SU4y1D77p/
  1. //<a href="https://www.luogu.com.cn/problem/P3381" target="_blank" rel="noopener"> Luogu P3381 【模板】最小费用最大流</a>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <queue>
  6. using namespace std;
  7. const int N=5010,M=100010,INF=1e8;
  8. int n,m,S,T;
  9. struct edge{int v,c,w,ne;}e[M];
  10. int h[N],idx=1;//从2,3开始配对
  11. int d[N],mf[N],pre[N],vis[N];
  12. int flow,cost;
  13. void add(int a,int b,int c,int d){
  14.   e[++idx]={b,c,d,h[a]};
  15.   h[a]=idx;
  16. }
  17. bool spfa(){
  18.   memset(d,0x3f,sizeof d);
  19.   memset(mf,0,sizeof mf);
  20.   queue<int> q; q.push(S);
  21.   d[S]=0, mf[S]=INF, vis[S]=1;
  22.   while(q.size()){
  23.     int u=q.front(); q.pop();
  24.     vis[u]=0;
  25.     for(int i=h[u];i;i=e[i].ne){
  26.       int v=e[i].v,c=e[i].c,w=e[i].w;
  27.       if(d[v]>d[u]+w && c){
  28.         d[v]=d[u]+w; //最短路
  29.         pre[v]=i;
  30.         mf[v]=min(mf[u],c);
  31.         if(!vis[v]){
  32.           q.push(v); vis[v]=1;
  33.         }
  34.       }
  35.     }
  36.   }
  37.   return mf[T]>0;
  38. }
  39. void EK(){
  40.   while(spfa()){
  41.     for(int v=T;v!=S;){
  42.       int i=pre[v];
  43.       e[i].c-=mf[T];
  44.       e[i^1].c+=mf[T];
  45.       v=e[i^1].v;
  46.     }
  47.     flow+=mf[T]; //累加可行流
  48.     cost+=mf[T]*d[T];//累加费用   
  49.   }
  50. }
  51. int main(){
  52.   scanf("%d%d%d%d",&n,&m,&S,&T);
  53.   int a,b,c,d;
  54.   while(m --){
  55.     scanf("%d%d%d%d",&a,&b,&c,&d);
  56.     add(a,b,c,d);
  57.     add(b,a,0,-d);
  58.   }
  59.   EK();
  60.   printf("%d %d\n",flow,cost);
  61.   return 0;
  62. }
复制代码
 

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

曹旭辉

金牌会员
这个人很懒什么都没写!
快速回复 返回顶部 返回列表