Description

Alice 和 Bob 在图论课程上学习了最大流和最小费用最大流的相关知识.

最大流问题: 给定一张有向图表示运输网络, 一个源点 \(S\) 和一个汇点 \(T\), 每条边都有最大流量. 一个合法的网络流方案必须满足:

  1. 每条边的实际流量都不超过其最大流量且非负;
  2. 除了源点 \(S\) 和汇点 \(T\) 之外, 对于其余所有点, 都满足该点总流入流量等于该点 总流出流量; 而 \(S\) 点的净流出流量等于 \(T\) 点的净流入流量, 这个值也即该网络流方案的总运输量.

最大流问题就是对于给定的运输网络, 求总运输量最大的网络流方案.

上图表示了一个最大流问题. 对于每条边, 右边的数代表该边的最大流量, 左边的数代表在最优解中, 该边的实际流量. 需要注意到, 一个最大流问题的解可能不是唯一的.

对于一张给定的运输网络, Alice 先确定一个最大流, 如果有多种解, Alice 可以任选一种; 之后 Bob 在每条边上分配单位花费 (单位花费必须是非负实数), 要求所有边的单位花费之和 等于 \(P\). 总费用等于每一条边的实际流量乘以该边的单位花费. 需要注意到, Bob 在分配单位花费之前, 已经知道 Alice 所给出的最大流方案.

现茌 Alice 希望总费用尽量小, 而 Bob 希望总费用尽量大. 我们想知道, 如果两个人都执行 最优策略, 最大流的值和总费用分别为多少.

Input

第一行三个整数 \(n, m, p\).\(n\) 表示给定运输网络中节点的数量,\(m\) 表示有向边的数量,\(p\) 的含义见问题描述部分. 为了简化问题, 我们假设源点 \(S\) 是点 \(1\), 汇点 \(T\) 是点 \(N\).

接下来 \(m\) 行, 每行三个整数 \(a, b, c\), 表示有一条从点 \(a\) 到点 \(b\) 的有向边, 其最大流量是 \(c\).

Output

第一行一个整数, 表示最大流的值.

第二行一个实数, 表示总费用. 建议选手输出四位以上小数.

Sample Input

3 2 1
1 2 10
2 3 15

Sample Output

10
10.0000

Data Range

对于 20% 的测试数据: 所有有向边的最大流量都是 1.

对于 100% 的测试数据:\(n \leq 100, m \leq 1000\).

对于 100% 的测试数据: 所有点的编号在 \([1, n]\) 范围内.\(1 \leq 每条边的最大流量 \leq 50000\).\(1 \leq p \leq 10\). 给定运输网络中不会有起点和终点相同的边.

Explanation

这道题太奇怪了~

首先分析一下题目, 其实是一道类似贪心的问题. 就是说 Bob 如果想要获得做大的花费, 那么他肯定会选择那条流量最大的边把权值调成 \(p\).

也就是说 Alice 要干的事就是把最大流量边流量最小化.

二分一下最大流量的边的流量然后判断一下是否可以跑出原来的最大流就可以了. 但是一个 奇怪的问题就来了:

本来我是写的整数版本的 (就是把所有边权统一乘上 \(10^6\), 然后输出时再转回来), 结果 不停地 WA 也没法发现错在哪里. 然后找到网上一个版本的是用的小数加 epsilon 的做法, 调了半个小时调出来了结果交上去 TLE......

就在审阅代码的时候发现新写的代码里第二组输出乘上了 \(p\), 然后把这个 \(p\) 加回到原来的程序里就 AC 了~

样例数据实在太坑人

下面附带的是那个 TLE 的代码:


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

using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 300, maxm = 2100;
const llf infinit = 1e15;
const llf epsilon = 1e-6;

class FiddledDinic
{
public:
    struct edge
    {
        int u, v;
        llf flow, init_flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, lli flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = p->init_flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = q->init_flow = 0.0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        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 > epsilon && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] > 0)
            return true;
        return false;
    }
    llf find(int p, llf mn)
    {
        if (p == t)
            return mn;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (ep->flow > epsilon && level[ep->v] == level[p] + 1) {
                llf tmp = find(ep->v, min(mn, ep->flow));
                if (tmp > epsilon) {
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                    return tmp;
                }
            }
        return 0.0;
    }
    llf eval_mf(llf max_allowed)
    {
        // Resetting edges' stati
        for (int i = 1; i <= ecnt; i++)
            epool[i].flow = min(epool[i].init_flow, max_allowed);
        // Really evaluating maximum flow
        llf max_flow = 0.0;
        while (make_level()) {
            llf tmp = infinit;
            do {
                tmp = find(s, max_allowed);
                max_flow += tmp;
            } while (tmp > epsilon);
        }
        return max_flow;
    }
    llf eval(llf required_mf)
    {
        llf l = 0.0, r = infinit;
        llf res = 0.0;
        while (r - l > epsilon) {
            llf mid = (l + r) / 2;
            llf max_flow = eval_mf(mid);
            if (fabs(required_mf - max_flow) < epsilon)
                r = mid;
            else
                l = mid;
        }
        return l;
    }
} graph;

int n, m;
llf P;

int main(int argc, char** argv)
{
    scanf("%d%d%lf", &n, &m, &P);
    graph.n = n;
    graph.s = 1;
    graph.t = n;
    for (int i = 1; i <= m; i++) {
        int a, b; lli c;
        scanf("%d%d%lld", &a, &b, &c);
        graph.add_edge(a, b, c);
    }
    llf mf = graph.eval_mf(infinit);
    printf("%lf\n", mf);
    llf fn_res = graph.eval(mf) * P;
    printf("%.4lf\n", fn_res);
    return 0;
}

Source Code


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

using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 300, maxm = 2100;
const lli infinit = 0x007f7f7f7f7f7f7fll;
const llf epsilon = 1e6;

class FiddledDinic
{
public:
    struct edge
    {
        int u, v;
        lli flow, init_flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, lli flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = p->init_flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = q->init_flow = 0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        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 find(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                lli tmp = find(ep->v, min(ep->flow, mn - sum));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    lli eval_mf(lli max_allowed)
    {
        // Resetting edge stati
        for (int i = 1; i <= ecnt; i++)
            epool[i].flow = min(epool[i].init_flow, max_allowed);
        // Really evaluating maximum flow
        lli max_flow = 0;
        while (make_level()) {
            lli tmp = find(s, max_allowed);
            if (tmp <= 0)
                break;
            max_flow += tmp;
        }
        return max_flow;
    }
    lli eval(lli required_mf)
    {
        lli l = 1, r = infinit;
        lli res = 0;
        while (l <= r) {
            lli mid = (l + r) / 2;
            lli max_flow = eval_mf(mid);
            if (max_flow >= required_mf)
                res = mid, r = mid - 1;
            else
                l = mid + 1;
        }
        return res;
    }
} graph;

int n, m;
lli P;

int main(int argc, char** argv)
{
    scanf("%d%d%lld", &n, &m, &P);
    graph.n = n;
    graph.s = 1;
    graph.t = n;
    for (int i = 1; i <= m; i++) {
        int a, b; lli c;
        scanf("%d%d%lld", &a, &b, &c);
        graph.add_edge(a, b, c*epsilon);
    }
    lli mf = graph.eval_mf(infinit);
    printf("%lld\n", mf / (lli)epsilon);
    lli fn_res_l = graph.eval(mf);
    llf fn_res = (llf)fn_res_l * P / epsilon;
    printf("%.4lf\n", fn_res);
    return 0;
}