题目地址：洛谷：【P2604】[ZJOI2010]网络扩容 – 洛谷、BZOJ：Problem 1834. — [ZJOI2010]network 网络扩容

题目描述

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。

输入输出格式

输入格式：
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

输出格式：
输出文件一行包含两个整数，分别表示问题1和问题2的答案。

输入输出样例

输入样例#1：

5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1

输出样例#1：

13 19

说明

30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10

题解

对于问题1，其实可以单独拿出来跑最大流，考虑问题2。我们在建边的时候建两种边，一种容量为c，费用为0，一种容量无限，费用为w，这样就可以实现扩容付费了。实际上问题2和问题1可以合在一起做，先跑一遍MCMF，注意当即将产生费用的时候终止，输出产生费用前的最大流，然后从源向1连边容量k费用0用于限制流量，从新源跑MCMF，可以将之前的残量网络利用起来避免重复跑MCMF。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int n, m, k;

int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];

inline bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0, sizeof(f));
    dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && dis[v] > dis[u] + gra[i].cost) {
                dis[v] = dis[u] + gra[i].cost;
                f[v] = std::min(gra[i].cap, f[u]);
                pre[v] = u; pree[v] = i;
                if(!inque[v]) {
                    inque[v] = true; que.push(v);
                }
            }
        }
    }
    return f[t] != 0;
}

int flow, cost;

inline void mcmf(int s, int t, bool flag) {
    while(spfa(s, t)) {
        if(flag && dis[t]) break;
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t];
            gra[pree[i] ^ 1].cap += f[t];
        }
        flow += f[t]; cost += dis[t] * f[t];
    }
}

int u, v, c, w;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint(); k = readint();
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint(); c = readint(); w = readint();
        addedge(u, v, c, 0);
        addedge(u, v, k, w);
    }
    mcmf(1, n, true);
    printf("%d ", flow);
    addedge(0, 1, k, 0);
    mcmf(0, n, false);
    printf("%d", cost);
    return 0;
}