BFS KM、HLPP、Primal-dual Dijkstra费用流，带Primal-dual Dijkstra的多路增广费用流（类Dinic算法）

BB

又是屯个板 QwQ
蒟蒻一直以为常见网络流算法中ISAP最快，然而冒出来个HLPP QAQ
蒟蒻一直以为费用流不会被卡，然后就被卡了 QAQ
蒟蒻一直以为DFS KM不会被卡，然后就被卡了 QAQ
（其实蒟蒻以前不会KM QAQ）

 

Introduction

 

二分图最大权匹配 - UOJ 80

Description
从前一个和谐的班级，有 nl 个是男生，有 nr 个是女生。编号分别为 1,…,nl 和 1,…,nr。
有若干个这样的条件：第 v 个男生和第 u 个女生愿意结为配偶，且结为配偶后幸福程度为 s。
请问这个班级里幸福程度之和最大是多少？
范围：1≤nl,nr≤400，1≤m≤160000，1≤w≤10^9
时限：1s
Sample Input

2 2 3
1 1 100
1 2 1
2 1 1

Sample Output

100
1 0

Solution - BFS KM
如果转为费用流，需要建成max(nl, nr) × max(nl, nr)的图，每条边流量都为1，然而复杂度不对 QAQ
使用O(n^3)的KM可过，但是本题卡DFS QAQ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)400 + 15;
const ll inf = 1LL << 60;

bool vx[N], vy[N];
ll lx[N], ly[N], slack[N], w[N][N];
int ml[N], mr[N], pre[N];
int que[N];

inline void setCrossRoad(int& v) {
    for(; v; swap(v, mr[pre[v]])) {
        ml[v] = pre[v];
    }
}

inline void bfs(int u, int n) {
    int head = 0, tail = 0;
    que[tail++] = u;
    vx[u] = true;
    while(true) {
        while(head != tail) {
            int u = que[head++];
            for(int v = 1; v <= n; v++) {
                if(vy[v]) {
                    continue;
                }
                ll d = lx[u] + ly[v] - w[u][v];
                if(d > slack[v]) {
                    continue;
                }
                pre[v] = u;
                if(d == 0) {
                    if(!ml[v]) {
                        setCrossRoad(v);
                        return;
                    }
                    vy[v] = vx[ml[v]] = true;
                    que[tail++] = ml[v];
                } else {
                    slack[v] = d;
                }
            }
        }
        ll d = inf;
        int to = 1;
        for(int v = 1; v <= n; v++) {
            if(!vy[v] && d > slack[v]) {
                d = slack[v];
                to = v;
            }
        }
        for(int i = 1; i <= n; i++) {
            if(vx[i]) {
                lx[i] -= d;
            }
            if(vy[i]) {
                ly[i] += d;
            } else {
                slack[i] -= d;
            }
        }
        if(!ml[to]) {
            setCrossRoad(to);
            return;
        }
        head = tail = 0;
        que[tail++] = ml[to];
        vx[ml[to]] = vy[to] = true;
    }
}

inline ll KM(int n) {
    for(int i = 1; i <= n; i++) {
        ly[i] = 0;
        ml[i] = mr[i] = 0;
        lx[i] = *max_element(w[i] + 1, w[i] + 1 + n);
    }
    for(int i = 1; i <= n; i++) {
        fill(vx, vx + 1 + n, false);
        fill(vy, vy + 1 + n, false);
        fill(slack, slack + 1 + n, inf);
        bfs(i, n);
    }
    return accumulate(lx + 1, lx + 1 + n, 0LL) + accumulate(ly + 1, ly + 1 + n, 0LL);
}

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    while(k--) {
        int u, v, val;
        scanf("%d%d%d", &u, &v, &val);
        w[u][v] = val;
    }
    ll ans = KM(max(n, m));
    printf("%lld\n", ans);
    for(int i = 1; i <= n; i++) {
        printf("%d ",  w[i][mr[i]] ? mr[i] : 0);
    }
}

 

【模板】最小费用最大流 - luogu 3381

Description
如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。
Sample Input

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

Sample Output

50 280

Solution 1 - Primal-dual Dijkstra

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = (int)5000 + 3;
const int M = (int)50000 + 3;

struct Node {
    int u;
    ll d;
    bool operator < (const Node& b) const {
        return d > b.d;
    }
};
struct edge {
    int v, nxt, flow;
    ll cost;
};

int flow[N];
int pre[N], cur[N];
ll dis[N], h[N];
edge e[M * 4];
int head[N], tot;

inline void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}

inline void addEdge(int u, int v, int flow, ll cost) {
    e[tot] = edge{v, head[u], flow, cost};
    head[u] = tot++;
    e[tot] = edge{u, head[v], 0, -cost};
    head[v] = tot++;
}

bool dijkstra(int src, int des, int n) {
    priority_queue<Node> que;
    fill(dis + 1, dis + n + 1, 1LL << 30);
    fill(flow + 1, flow + n + 1, 1LL << 30);
    dis[src] = 0, pre[src] = src;
    que.push(Node{src, 0});
    while(!que.empty()) {
        Node ele = que.top();
        que.pop();
        int u = ele.u;
        ll d = ele.d;

        if(d > dis[u]) {
            continue;
        }

        for(int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if(e[i].flow && dis[v] > dis[u] + e[i].cost + h[u] - h[v]) {
                dis[v] = dis[u] + e[i].cost + h[u] - h[v];
                flow[v] = min(flow[u], e[i].flow);
                pre[v] = u;
                cur[v] = i;
                que.push(Node{v, dis[v]});
            }
        }
    }
    return dis[des] != (1LL << 30);
}

pair<int, ll> solve(int src, int des, int n) {
    int maxFlow = 0;
    ll minCost = 0;
    while(dijkstra(src, des, n)) {
        int aug = flow[des];
        maxFlow += aug;
        minCost += aug * (dis[des] - h[src] + h[des]);
        for(int u = pre[des], v = des; v != src; v = u, u = pre[u]) {
            e[cur[v]].flow -= aug;
            e[cur[v] ^ 1].flow += aug;
        }
        for(int i = 1; i <= n; i++) {
            h[i] += dis[i];
        }
    }
    return make_pair(maxFlow, minCost);
}

int main() {
    init();
    int n, m, src, des;
    scanf("%d%d%d%d", &n, &m, &src, &des);
    while(m--) {
        int u, v, w, f;
        scanf("%d%d%d%d", &u, &v, &w, &f);
        addEdge(u, v, w, f);
    }
    pair<int, ll> res = solve(src, des, n);
    printf("%d %lld\n", res.first, res.second);
}

Solution 2 - 带Primal-dual Dijkstra的多路增广算法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = (int)5000 + 3;
const int M = (int)50000 + 3;
const int inf = 1LL << 30;

struct Node {
    int u;
    ll d;
    bool operator < (const Node& b) const {
        return d > b.d;
    }
};
struct edge {
    int v, nxt, flow;
    ll cost;
};

int G[N][N];
edge e[M * 4];
int head[N], tot;
int cur[N];
bool used[N];
ll dis[N], h[N];

inline void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}

inline void addEdge(int u, int v, int flow, ll cost) {
    e[tot] = edge{v, head[u], flow, cost};
    head[u] = tot++;
    e[tot] = edge{u, head[v], 0, -cost};
    head[v] = tot++;
}

bool dijkstra(int src, int des, int n) {
    priority_queue<Node> que;
    fill(dis + 1, dis + n + 1, inf);
    memcpy(cur, head, sizeof(head));
    dis[des] = 0;
    que.push(Node{des, 0});
    while(!que.empty()) {
        Node ele = que.top();
        que.pop();
        int u = ele.u;
        ll d = ele.d;

        if(d > dis[u]) {
            continue;
        }

        for(int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if(e[i^1].flow && dis[v] > dis[u] - e[i].cost + h[u] - h[v]) {
                dis[v] = dis[u] - e[i].cost + h[u] - h[v];
                que.push(Node{v, dis[v]});
            }
        }
    }
    return dis[src] != inf;
}

int dfs(int u, int des, int low, ll& totalCost) {
    if(u == des) {
        return low;
    }
    used[u] = true;
    int sum = 0;
    for(int& i = cur[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        ll du = (dis[u] - h[des] + h[u]);
        ll dv = (dis[v] - h[des] + h[v]);
        if(!used[v] && e[i].flow && du - e[i].cost == dv) {
            int aug = dfs(v, des, min(e[i].flow, low - sum), totalCost);
            if(aug) {
                e[i].flow -= aug;
                e[i ^ 1].flow += aug;
                sum += aug;
                totalCost += 1LL * aug * e[i].cost;
            }
            if(sum == low) {
                break;
            }
        }
    }
    used[u] = false;
    return sum;
}

inline void initH(int src, int des, int n) {
    static bool inq[N];
    fill(dis + 1, dis + n + 1, inf);
    dis[des] = 0;
    queue<int> que;
    que.push(des);
    inq[des] = true;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for(int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if(e[i^1].flow && dis[v] > dis[u] - e[i].cost) {
                dis[v] = dis[u] - e[i].cost;
                if(!inq[v]) {
                    inq[v] = true;
                    que.push(v);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        h[i] = dis[i];
    }
}

inline pair<int, ll> solve(int src, int des, int n) {
    initH(src, des, n);    //非负权图可不执行
    pair<int, ll> pr(0, 0LL);
    while(dijkstra(src, des, n)) {
        while(true) {
            int x = dfs(src, des, inf, pr.second);
            pr.first += x;
            if(!x) {
                break;
            }
        }
    }
    return pr;
}

int main() {
    init();
    int n, m, src, des;
    scanf("%d%d%d%d", &n, &m, &src, &des);
    while(m--) {
        int u, v, w, f;
        scanf("%d%d%d%d", &u, &v, &w, &f);
        addEdge(u, v, w, f);
    }
    pair<int, ll> res = solve(src, des, n);
    printf("%d %lld\n", res.first, res.second);
}

 

【模板】最大流 加强版 / 预流推进 - luogu 4722

Description
给定 n 个点，m 条有向边，给定每条边的容量，求从点 s 到点 t 的最大流。 Sample Input

7 14 1 7
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7
10 16 1 2
1 3 2
1 4 2
5 2 2
6 2 2
3 5 1
3 6 1
4 5 1
4 6 1
1 7 2147483647
9 2 2147483647
7 8 2147483647
10 9 2147483647
8 5 2
8 6 2
3 10 2
4 10 2

Sample Output

14
8

Solution - HLPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1200 + 15;
const int M = (int)120000 + 15;
const int inf = 0x3f3f3f3f;

struct edge {
    int v, nxt, flow;
};

edge e[M * 2];
int head[N], tot, ht[N], ex[N], gap[N << 1];

struct cmp {
    inline bool operator () (int a, int b) const {
        return ht[a] < ht[b];
    }
};
priority_queue<int, vector<int>, cmp> que;
bool inq[N];

inline void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}

inline void addEdge(int u, int v, int flow) {
    e[tot] = edge{v, head[u], flow};
    head[u] = tot++;
    e[tot] = edge{u, head[v], 0};
    head[v] = tot++;
}

inline bool bfsInit(int src, int des, int n) {
    memset(ht, 0x3f, sizeof(ht));
    queue<int> que;
    que.push(des);
    ht[des] = 0;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if(e[i ^ 1].flow && ht[v] > ht[u] + 1) {
                ht[v] = ht[u] + 1;
                que.push(v);
            }
        }
    }
    return ht[src] != inf;
}

inline bool push(int u, int src, int des) {
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v, w = e[i].flow;
        if(!w || ht[u] != ht[v] + 1) {
            continue;
        }
        int k = min(w, ex[u]);
        ex[u] -= k;
        ex[v] += k;
        e[i].flow -= k;
        e[i ^ 1].flow += k;
        if(v != src && v != des && !inq[v]) {
            que.push(v);
            inq[v] = true;
        }
        if(!ex[u]) {
            return false;
        }
    }
    return true;
}

inline void relabel(int u) {
    ht[u] = inf;
    for(int i = head[u]; ~i; i = e[i].nxt) {
        if(e[i].flow) {
            ht[u] = min(ht[u], ht[e[i].v] + 1);
        }
    }
}

inline int hlpp(int src, int des, int n) {
    if(!bfsInit(src, des, n)) {
        return 0;
    }
    ht[src] = n;
    memset(gap, 0, sizeof(gap));
    for(int i = 1; i <= n; i++) {
        if(ht[i] != inf) {
            gap[ht[i]]++;
        }
    }
    for(int i = head[src]; ~i; i = e[i].nxt) {
        int v = e[i].v, w = e[i].flow;
        if(!w) {
            continue;
        }
        ex[src] -= w;
        ex[v] += w;
        e[i].flow -= w;
        e[i ^ 1].flow += w;
        if(v != src && v != des && !inq[v]) {
            que.push(v);
            inq[v] = true;
        }
    }
    while(!que.empty()) {
        int u = que.top();
        que.pop();
        inq[u] = false;
        if(push(u, src, des)) {
            if((--gap[ht[u]]) == 0) {
                for(int v = 1; v <= n; v++) {
                    if(v != src && v != des && ht[v] > ht[u] && ht[v] < n + 1) {
                        ht[v] = n + 1;
                    }
                }
            }
            relabel(u);
            gap[ht[u]]++;
            que.push(u);
            inq[u] = true;
        }
    }
    return ex[des];
}

int main() {
    init();
    int n, m, src, des;
    scanf("%d%d%d%d", &n, &m, &src, &des);
    while(m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
    }
    printf("%d", hlpp(src, des, n));
    return 0;
}