最小费用最大流

Obito · 2020-02-26 18:03:14 · 个人记录

最小费用最大流：在找到最大流的基础上，保证费用最少。

简称：MCMF

dijkstra+EK

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100010, M = 200010;
int head[N], to[M], flow[M], nxt[M], increase[N], pre[N], cost[N], dis[N];
bool vis[N];
int n, m, s, t, tot;
long long ans, maxflow;
void add(int x, int y, int z, int c) 
{
    to[++tot] = y;
    flow[tot] = z;
    cost[tot] = c;
    nxt[tot] = head[x];
    head[x] = tot;
    //反向 
    to[++tot] = x;
    flow[tot] = 0;
    cost[tot] = -c;
    nxt[tot] = head[y];
    head[y] = tot;
    return ;
}

bool spfa() 
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    memset(increase, 0x7f, sizeof(increase));
    queue<int> q;
    q.push(s); 
    vis[s] = true;
    dis[s] = 0;
    while(q.empty() == false) 
    {
        int x = q.front(); 
        q.pop();
        vis[x] = false;
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = to[i];
            if(flow[i] > 0 && dis[x] + cost[i] < dis[y])  //容量不为0 
            {
                dis[y] = dis[x] + cost[i];
                increase[y] = min(increase[x], flow[i]);
                pre[y] = i;
                if(vis[y] == false)
                {
                    q.push(y);
                    vis[y] = true;
                }
            }
        }
    }
    return dis[t] < 0x7f7f7f7f;
}

void update() // 更新增广路及其残余网络 
{ 
    int cur = t;
    while(cur != s)
    {
        int last = pre[cur];
        flow[last] -= increase[t];
        flow[last ^ 1] += increase[t]; // xor 反边 
        cur = to[last ^ 1];
    }
    maxflow += increase[t];
    ans += dis[t] * increase[t];
    return ;
}

int main() 
{
    cin >> n >> m >> s >> t;
    memset(head, 0, sizeof(head));
    tot = 1; //注意异或 
    maxflow = 0;
    for(int i = 1; i <= m; i++) 
    {
        int x, y, z, c;
        cin >> x >> y >> z >> c;
        add(x, y, z, c);
    }
    while(spfa() == true) 
        update();
    cout << maxflow << " " << ans;
    return 0;
}