Description

给定一张有向图, 每条边都有一个容量 \(C\) 和一个扩容费用 \(W\). 这里扩容费用是指将容量扩大 \(1\) 所需的费用. 求:

  1. 在不扩容的情况下,\(1\) 到 \(N\) 的最大流
  2. 将 \(1\) 到 \(N\) 的最大流增加 \(K\) 所需的最小扩容费用.

Input

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

Output

输出文件一行包含两个整数, 分别表示问题 1 和问题 2 的答案.

Sample Input

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

Sample Output

13 19

Data Range

30% 的数据中,\(N \leq 100\)

100% 的数据中,\(N \leq 1000, M \leq 5000, K \leq 10\)

Explanation

第一问很简单, 按数据建图, 然后一遍最大流算法即可.

第二问则需要用最小费用最大流算法, 主要是建图, 那么可以从第一问的残留网络上继续 建图, 对残留网络上的每一条边建一条容量是 \(\infty\) 费用是 \(W\) 的边 (反向弧容量为 \(0\), 费用为 \(-W\)) , 然后建一个超级源点, 从超级源向 \(1\) 建一条容量为 \(K\), 费用为 \(0\) 的边, 对这个图进行最小费用最大流算法.

最小费用最大流操作:

  1. 首先要对于这道题的图来说, 有的边需要花费费用, 而有的又不用, 而不用扩容的边费用为 \(0\), 需要扩容的边费用为 \(W\), 容量无限, 这就是本题这样建图的原因.
  2. 对于残留网络进行费用最短路 SPFA 算法, 不用扩容的边一定会选费用为 \(0\) 的边, 然后记录路径, 找最小容量对可行路进行增流, 更新 \(res\)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 1010, maxm = 500100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class MixedMaximumFlow
{
public:
    struct edge
    {
        int u, v;
        lli flow, cost, temp_cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    // Reserved for Dinic
    int level[maxn];
    void add_edge(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->temp_cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->temp_cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    void add_edge_spfa(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        queue<int> que;
        memset(level, 0, sizeof(level));
        que.push(s);
        level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
            if (level[t] > 0)
                return true;
        }
        return false;
    }
    lli dfs(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = dfs(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    // Reserved for SPFA MCMF
    lli dist[maxn];
    bool inque[maxn];
    edge *from[maxn];
    bool spfa(void)
    {
        queue<int> que;
        for (int i = 1; i <= n; i++)
            dist[i] = infinit, inque[i] = false, from[i] = NULL;
        que.push(s);
        dist[s] = 0, inque[s] = true;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next) {
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            }
            inque[p] = false;
        }
        if (dist[t] < infinit)
            return true;
        return false;
    }
    void reload_graph(int k)
    {
        n = n + 1;
        s = n;
        int o_ecnt = ecnt;
        for (int i = 1; i <= o_ecnt; i += 2)
            if (i % 2 == 1) {
                edge *ep = &epool[i];
                add_edge_spfa(ep->u, ep->v, infinit, ep->temp_cost);
            }
        add_edge_spfa(s, 1, k, 0);
        return ;
    }
    // Global indexing functions
    lli eval_max_flow(void)
    {
        lli sum = 0;
        while (make_level()) {
            lli tmp = dfs(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
    lli eval_min_cost(void)
    {
        lli max_flow = 0,
            min_cost = 0;
        while (spfa()) {
            lli tmp = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                tmp = min(tmp, ep->flow);
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                ep->flow -= tmp,
                ep->rev->flow += tmp;
            max_flow += tmp;
            min_cost += tmp * dist[t];
        }
        return min_cost;
    }
} graph;

int n, m, K;

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &m, &K);
    graph.n = n;
    graph.s = 1;
    graph.t = n;
    for (int i = 1; i <= m; i++) {
        int u, v, w, c;
        scanf("%d%d%d%d", &u, &v, &w, &c);
        graph.add_edge(u, v, w, c);
    }
    // Subproblem #1
    lli res_1 = graph.eval_max_flow();
    // Subproblem #2
    graph.reload_graph(K);
    lli res_2 = graph.eval_min_cost();
    printf("%lld %lld\n", res_1, res_2);
    return 0;
}