【模板】(最小费用)最大流

网络最大流

P3376 【模板】网络最大流

一、\(Edmonds-Karp\)算法

不断在残量网络\(dfs\)进行增广，当不能进行增广时，即为最大流。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e4 + 5, M = 2e5 + 5;
int n, m, s, t, pre[M], vis[N];
int cnt = 1, head[N], to[M], nxt[M], val[M];
void add(int u, int v, int w) {
    to[++ cnt] = v; val[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt;
}
bool bfs() {
    queue <int> q; q.push(s);
    memset(vis, 0, sizeof(vis));
    memset(pre, 0, sizeof(pre));
    vis[s] = 1;
    while(! q.empty()) {
        int x = q.front(); q.pop();
        if(x == t) return true;
        for(int i = head[x]; i ; i = nxt[i]) {
            if(vis[to[i]] == 1 || val[i] == 0) continue;
            pre[to[i]] = i;
            q.push(to[i]), vis[to[i]] = 1;
        }
    }
    return false;
}
int EK() {
    int ans = 0;
    while(bfs()) {
        int up = 2e9;
        for(int p = t; p != s; p = to[pre[p] ^ 1]) up = min(up, val[pre[p]]);
        for(int p = t; p != s; p = to[pre[p] ^ 1]) {
            val[pre[p]] -= up;
            val[pre[p] ^ 1] += up;
        }
        ans += up;
    }
    return ans;
}
int main() {

    cin >> n >> m >> s >> t;
    for(int i = 1, u, v, w; i <= m; i ++) {
        cin >> u >> v >> w;
        add(u, v, w); add(v, u, 0);
    }
    cout << EK() << endl;
    return 0;
}

二、\(Dinc\)算法

在残量网络上\(bfs\)构建分层图，再从分层图上\(dfs\)不断增广。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e4 + 5, M = 2e5 + 5, INF = 2e9;
int n, m, s, t, flow, dep[N];
int cnt = 1, head[N], to[M], nxt[M], val[M];
void add(int u, int v, int w) {
    to[++ cnt] = v; val[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt;
}
bool bfs() {
    memset(dep, 0, sizeof(dep));
    queue <int> q; q.push(s);
    dep[s] = 1;
    while(! q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; i ; i = nxt[i]) {
            if(dep[to[i]] || val[i] <= 0) continue;
            dep[to[i]] = dep[x] + 1;
            q.push(to[i]);
        }
    }
    return dep[t] > 0;
}
int dfs(int x, int flow) {
    if(x == t) return flow;
    int up = 0;
    for(int i = head[x]; i ; i = nxt[i]) {
        if(val[i] == 0 || dep[to[i]] != dep[x] + 1) continue;
        int tmp = dfs(to[i], min(flow, val[i]));
        if(tmp == 0) continue;
        val[i] -= tmp;
        val[i ^ 1] += tmp;
        up += tmp; flow -= tmp;
        if(flow == 0) return up;
    }
    return up;

}
int Dinic() {
    int ans = 0;
    while(bfs()) while(flow = dfs(s, INF)) ans += flow;
    return ans;
}
int main() {
    cin >> n >> m >> s >> t;
    for(int i = 1, u, v, w; i <= m; i ++) {
        cin >> u >> v >> w;
        add(u, v, w); add(v, u, 0);
    }
    cout << Dinic() << endl;
    return 0;
}

不过，在加入当前弧优化和快读后，它跑了\(148ms\).(只加当前弧优化时跑\(287ms\))

当前弧优化：加速跳过枚举不必要的边。

注意在每次\(bfs\)前对\(cur\)重新赋值。

核心code:

bool bfs() {
    for(int i = 1;i <= n;i ++) cur[i] = head[i];
    memset(dep, 0, sizeof(dep));
    queue <int> q; q.push(s);
    dep[s] = 1;
    while(! q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; i ; i = nxt[i]) {
            if(dep[to[i]] || val[i] <= 0) continue;
            dep[to[i]] = dep[x] + 1;
            q.push(to[i]);
        }
    }
    return dep[t] > 0;
}
int dfs(int x, int flow) {
    if(x == t) return flow;
    int up = 0;
    for(int &i = cur[x]; i ; i = nxt[i]) {
        if(val[i] == 0 || dep[to[i]] != dep[x] + 1) continue;
        int tmp = dfs(to[i], min(flow, val[i]));
        if(tmp == 0) continue;
        val[i] -= tmp;
        val[i ^ 1] += tmp;
        up += tmp; flow -= tmp;
        if(flow == 0) return up;
    }
    return up;
}

最小费用最大流

P3381 【模板】最小费用最大流

最小费用流

将\(bfs\)改为\(spfa\)跑最小费用即可。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e4 + 5, M = 2e5 + 5;
int n, m, s, t, ans, res, pre[M], vis[N], dis[N];
int cnt = 1, head[N], to[M], nxt[M], val[M], cost[M];
void add(int u, int v, int w, int c) {
    to[++ cnt] = v; val[cnt] = w; cost[cnt] = c;
    nxt[cnt] = head[u]; head[u] = cnt;
}
bool spfa() {
    queue <int> q; q.push(s);
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    vis[s] = 1; dis[s] = 0;
    while(! q.empty()) {
        int x = q.front(); q.pop();
        vis[x] = false;
        for(int i = head[x]; i ; i = nxt[i]) {
            if(val[i] && dis[to[i]] > dis[x] + cost[i]) {
                pre[to[i]] = i;
                dis[to[i]] = dis[x] + cost[i];
                if(vis[to[i]] == 0) q.push(to[i]), vis[to[i]] = true;
            }
        }
    }
    return dis[t] != 0x3f3f3f3f;
}
void EK() {
    while(spfa()) {
        int up = 2e9;
        for(int p = t; p != s; p = to[pre[p] ^ 1]) up = min(up, val[pre[p]]);
        for(int p = t; p != s; p = to[pre[p] ^ 1]) {
            val[pre[p]] -= up;
            val[pre[p] ^ 1] += up;
        }
        res += up * dis[t];
        ans += up;
    }
}
int main() {
    cin >> n >> m >> s >> t;
    for(int i = 1, u, v, w, c; i <= m; i ++) {
        cin >> u >> v >> w >> c;
        add(u, v, w, c); add(v, u, 0, -c);
    }
    EK();
    cout << ans << " " << res << endl;
    return 0;
}