QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 2048 MB
统计

题目描述

给定一张 $n$ 个点 $m$ 条边的有向图,其中源点为 $s$ 点,终点为 $t$ 点。每条边有起点 $a_i$,终点 $b_i$,流量下界 $l_i$,流量上界 $u_i$,费用 $c_i$。

现在,你需要找到一个从 $s$ 到 $t$ 的流,满足每个点的流量平衡与每条边的流量上下界,且在流量最大的情况下费用尽可能小。

输入格式

输入的第一行包含四个整数 $n, m, s, t$。

接下来 $m$ 行,每行包含五个整数 $a_i, b_i, l_i, u_i, c_i$。

输出格式

如果不存在合法流,则输出一行一个整数 -1

否则,输出一行两个整数,第一个整数表示最大流量,第二个整数表示在流量最大的情况下的最小费用。

样例数据

样例 1 输入

3 3 1 3
1 2 0 6 0
2 3 1 1000 4
2 3 0 1000 3

样例 1 输出

6 19

样例 2 输入

5 6 2 4
2 1 1 6 4
2 3 0 5 1
1 3 2 8 2
3 4 1 7 1
3 5 0 4 1
5 4 1 5 2

样例 2 输出

11 60

样例 3 输入

3 1 1 3
2 3 1 100 -100

样例 3 输出

-1

样例 4 输入

7 21 6 2
4 2 5838 564426 865577
2 4 138826 402418 671157
3 2 123701 426813 -543072
4 7 98453 297069 -986761
4 1 21240 326890 -393845
6 7 2698 993886 -59647
4 6 82877 385922 -912546
7 4 25734 366246 285364
7 1 69448 399825 -401006
3 6 22302 805072 919199
6 3 124308 353738 -384169
3 5 139305 535596 -570512
5 2 81261 479615 -662499
4 2 17109 716121 -195178
7 3 7838 518193 274351
6 4 60957 638462 -423334
7 2 56175 606681 -703583
6 3 35947 112359 -495175
1 3 90688 695522 618674
6 3 26527 999630 -429406
5 7 58044 610148 862096

样例 4 输出

2313184 -1814133530696

提示

对于所有数据,保证 $1 \le n \le 1\,000$,$1 \le m \le 5\,000$,$1 \le s,t \le n$,$s \ne t$。

对于所有数据,保证 $1 \le a_i, b_i \le n$,$a_i \ne b_i$,$1 \le l_i \le u_i \le 10^6$,$-10^6 \le c_i \le 10^6$。

特别地,保证本题的数据通过以下方式随机生成:

  1. 选定 $n$,$m$,$s$,$t$ 的值,不保证 $n,m,s,t$ 随机生成。
  2. 通过以下方式生成一张 $m$ 条边的有向图 $G$:
    1. 选定参数 $k_1, k_2$,满足 $0 \le k_1, k_2$ 且 $k_1 + k_2 \le n$。
    2. 进行 $k_1$ 次:
      • 均匀随机选择 $1 \le a \le n$ 且 $a \ne s$,添加边 $s \to a$。
    3. 进行 $k_2$ 次:
      • 均匀随机选择 $1 \le a \le n$ 且 $a \ne t$,添加边 $a \to t$。
    4. 进行 $m-k_1-k_2$ 次:
      • 均匀随机地选择 $1 \le a, b \le n$ 且 $a \ne b$,添加边 $a \to b$。
  3. 对于每条边,均匀随机地选择其费用 $c_i \in [-10^6, 10^6]$。
  4. 对于每条边,选择一个 $\Delta_i \in [1, 10^6]$,不保证 $\Delta_i$ 随机生成
  5. 随机进行以下过程若干次:
    1. 选择一个值 $\delta \in [1, 10^6]$,不保证 $\delta$ 随机生成。
    2. 从 $s$ 开始 dfs 整张图,每次均匀随机地选择一个出边。
    3. 如果最终到达了点 $t$,则将 $s \to t$ 路径上所有边的 $l_i$ 增加 $\delta$。
    4. 特别地,若存在边的 $l_i$ 超过了 $10^6 - \Delta_i - \delta$,则放弃本轮操作。
  6. 随机进行以下过程若干次:
    1. 选择一个值 $\delta \in [1, 10^6]$,不保证 $\delta$ 随机生成。
    2. 均匀随机地选择一个顶点 $x$。
    3. 从 $x$ 开始 dfs 整张图,每次均匀随机地选择一个出边。
    4. 如果最终回到了点 $x$,则将走过的路径上所有边的 $l_i$ 增加 $\delta$。
    5. 特别地,若存在边的 $l_i$ 超过了 $10^6 - \Delta_i - \delta$,则放弃本轮操作。
  7. 令每条边的 $u_i = l_i + \Delta_i$。