1. 无负环最小费用最大流

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int inque[MAXnd + 10], dis[MAXnd + 10], lim[MAXnd + 10], pre[MAXnd + 10];
queue<int> que;
void Spfa(int s) {
    memset(inque, 0, sizeof(inque));
    memset(dis, 0x3f, sizeof(dis));
    memset(lim, 0x3f, sizeof(lim));
    memset(pre, 0, sizeof(pre));
    dis[s] = 0;
    que.push(s); inque[s] = 1;
    while (!que.empty()) {
        int cur = que.front(); que.pop(); inque[cur] = 0;
        for (int i = head[cur]; i; i = nex[i]) {
            if (!cap[i]) continue;
            if (dis[to[i]] > dis[cur] + wei[i]) {
                dis[to[i]] = dis[cur] + wei[i];
                lim[to[i]] = min(lim[cur], cap[i]);
                pre[to[i]] = i;
                if (!inque[to[i]]) {
                    que.push(to[i]); inque[to[i]] = 1;
                }
            }
        }
    }
}

void Ek(int s, int t, int &ansf, int &anscos) {
    ansf = 0, anscos = 0;
    while (Spfa(s), dis[t] != INF) {
        ansf += lim[t];
        anscos += lim[t] * dis[t];
        for (int eg = pre[t]; eg; eg = pre[to[eg ^ 1]]) {
            cap[eg] -= lim[t]; cap[eg ^ 1] += lim[t];
        }
    }
}

2. 有负环最小费用最大流

P7173 【模板】有负圈的费用流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n, m, s1, t1, s2, t2, ans1, ans2;
int startf[MAXnd + 10];
int ansf, anscos;
signed main() {
    cntnex = 1;
    read(n, m, s1, t1);
    s2 = n + 1, t2 = n + 2;
    for (int i = 1, u, v, c, w; i <= m; ++i) {
        read(u, v, c, w);
        if (w >= 0) {
            Insert(u, v, c, w); Insert(v, u, 0, -w);
        } else if (w < 0) {
            startf[u] -= c, startf[v] += c;
            ans2 += w * c;
            Insert(u, v, 0, w); Insert(v, u, c, -w);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (startf[i] > 0) {
            Insert(s2, i, startf[i], 0); Insert(i, s2, 0, 0);
        } else if (startf[i] < 0) {
            Insert(i, t2, -startf[i], 0); Insert(t2, i, 0, 0);
        }
    }
    Insert(t1, s1, INF, 0); Insert(s1, t1, 0, 0);
    Ek(s2, t2, ansf, anscos);
    ans1 += cap[cntnex]; ans2 += anscos;
    head[s1] = nex[head[s1]]; head[t1] = nex[head[t1]]; cntnex -= 2;
    Ek(s1, t1, ansf, anscos);
    ans1 += ansf; ans2 += anscos;
    printf("%d %d\n", ans1, ans2);
    return 0;
}