洛谷 P3381 最小费用最大流(模板)

最小费用最大流

原来最小费用最大流只是在最小费用流的基础上去掉固定流f，任其找最短路去增广，直到不能找到最短路了(dis[t] == INF)就退出

洛谷P3381最小费用最大流

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 5005;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;///first:最短距离 second:节点编号
typedef long long ll;

struct edge{ int to, w, cap, rev; };

int n, m, s, t;
ll flow, res;
vector<edge> vec[N];
int h[N], dis[N];///节点的势 最短距离
int fro_v[N], fro_e[N];///vector 的 第一维和第二维
///用于确定最短路中点k前面那条边

void add(int from, int to, int w, int cap)
{
    int from_sz = vec[from].size(), to_sz = vec[to].size();
    vec[from].push_back( (edge){ to, w, cap, to_sz } );
    vec[to].push_back( (edge){ from, -w, 0, from_sz } );
}

void min_cost_flow(int s, int t)
{
    memset(h, 0, sizeof(h));
    while(1)
    {
        priority_queue<P, vector<P>, greater<P> > q;
        memset(dis, INF, sizeof(dis));
        dis[s] = 0;
        q.push(P(0, s));
        while(!q.empty())
        {
            P now = q.top();
            q.pop();
            int to = now.second;
            if(dis[to] < now.first)
                continue;
            for(int i = 0; i < vec[to].size(); ++i)
            {
                edge & nxt = vec[to][i];
                if(nxt.cap > 0 && dis[nxt.to] > dis[to] + nxt.w + h[to] - h[nxt.to])
                {
                    dis[nxt.to] = dis[to] + nxt.w + h[to] - h[nxt.to];
                    fro_v[nxt.to] = to;
                    fro_e[nxt.to] = i;
                    q.push(P(dis[nxt.to], nxt.to));
                }
            }
        }
        if(dis[t] == INF)
            return ;
        for(int v = 0; v <= n; ++v)
            h[v] += dis[v];

        int d = INF;
        for(int v = t; v != s; v = fro_v[v])
            d = min(d, vec[ fro_v[v] ][ fro_e[v] ].cap);

        flow += d;
        res += d * h[t];///There is a h[t] in Dijkstra, not a dis[t](in Bellman_Ford).
        for(int v = t; v != s; v = fro_v[v])///更新残余网络，建反向边
        {
            edge & nxt = vec[ fro_v[v] ][ fro_e[v] ];
            nxt.cap -= d;
            vec[v][nxt.rev].cap += d;
        }
    }
    return ;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    int ui, vi, wi, fi;
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d%d", &ui, &vi, &wi, &fi);
        add(ui, vi, fi, wi);
    }
    min_cost_flow(s, t);
    cout << flow << ' ' << res << '\n';
    return 0;
}