前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最小费用最大流 + dijkstra 模版(处理负边)

最小费用最大流 + dijkstra 模版(处理负边)

作者头像
用户2965768
发布2019-08-14 14:29:58
7150
发布2019-08-14 14:29:58
举报
文章被收录于专栏:wym

概念

在同一个网络中,可能存在多个总流量相同的最大流,我们可以在计算流量的基础之上,给网络中的弧增加一个单位流量费用(简称费用),在确保流量最大的前提下总费用最小——最小费用最大流。

代码语言:javascript
复制
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXN_ 5050
#define INF 0x3f3f3f3f
#define P pair<int,int>
using namespace std;
struct edge{ int to,cap,cost,rev;};
int n,m,flow,s,t,cap,res,cost,from,to,h[MAXN_];
std::vector<edge> G[MAXN_];
int dist[MAXN_],prevv[MAXN_],preve[MAXN_]; // 前驱节点和对应边
inline void add()
{
    G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
    G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
} // 在vector 之中找到边的位置所在!
inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9'){if(c=='-')flag=1;    c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?-x:x;
}
inline void min_cost_flow(int s,int t,int f)
{
    fill(h+1,h+1+n,0);
    while(f > 0)
    {
        priority_queue<P,vector<P>, greater<P> > D;
        memset(dist,INF,sizeof dist);
        dist[s] = 0; D.push(P(0,s));
        while(!D.empty())
        {
            P now = D.top(); D.pop();
            if(dist[now.second] < now.first) continue;
            int v = now.second;
            for(int i=0;i<(int)G[v].size();++i)
            {
                edge &e = G[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
                {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    D.push(P(dist[e.to],e.to));
                }
            }
        }
        // 无法增广 , 就是找到了答案了!
        if(dist[t] == INF) break;
        for(int i=1;i<=n;++i) h[i] += dist[i]; 
        int d = f;
        for(int v = t; v != s; v = prevv[v])
            d = min(d,G[prevv[v]][preve[v]].cap);
        f -= d; flow += d;
        res += d * h[t];
        for(int v=t;v!=s;v=prevv[v])
        {
            edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
}
int main()
{
   n = read(); m = read(); s = read(); t = read();
   for(int i=1;i<=m;++i)
   {
           from = read(); to = read(); cap = read(); cost = read();
           add();
   }
   min_cost_flow(s,t,INF);
   printf("%d %d\n",flow,res);
   return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年07月30日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档