← 返回题目列表

Codeforces · 843/E

E. 最大流量

中文机器翻译题面 查看原题

给定一个有向图,由 n 个顶点和 m 个边组成。顶点 s 和 t 分别标记为源和汇。此外,不存在以 s 结束的边,也不存在以 t 开始的边。

该图是按以下方式构建的:最初,每条边的容量 ci > 0。在此流网络中构建了源位于 s 、汇位于 t 的最大流。我们将 fi 表示为通过索引为 i 的边的流量值。接下来,所有容量ci和流量值fi被擦除。相反,指标 gi 写在边上——如果通过边 i 的流量值为正,即如果 fi > 0 则为 1,否则为 0。

使用图形和值 gi,找出初始流量网络中可能饱和的最小可能边数是多少(通过的流量等于容量,即 fi = ci)。并构建相应的流量网络,其中流量最大。

有向图中的流由每条边上的流值 fi 描述,从而满足以下条件:

- 对于每个顶点,除了源和汇之外,总流入流量和总流出流量相等,
- 对于每条边 0 ≤ fi ≤ ci

如果来自源的边上的流量值之和与到源的边上的流量值之和(本问题中没有这样的情况)之间的差值是最大可能的,则流量是最大的。

输入

输入数据的第一行包含四个正整数 n, m, s, t (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — 对应的顶点数、边数、源顶点索引和汇顶点索引。

接下来 m 行输入数据中的每一行都包含非负整数 ui, vi, gi (1 ≤ ui, vi ≤ n, $$g_i \in \{0, 1\}$$) — 边 i 的开头、边 i 的结尾和指示符,如果通过边 i 的流量值为正,则等于 1,否则等于 0。

保证没有边将顶点与其自身连接。此外,还保证每个有序顶点对之间不存在超过一条边,并且至少存在一个满足输入数据的所有约束的网络流。

输出

在第一行中打印单个非负整数 k — 最小边数,在最大流中应饱和。

在接下来的 m 行中,每一行打印两个整数 fi, ci (1 ≤ ci ≤ 109, 0 ≤ fi ≤ ci) — 通过边 i 的流量值和边 i 的容量。

该数据应在流量网络中形成正确的最大流量。此外,必须恰好有 k 条边满足 fi = ci 语句。另外,当且仅当 gi = 1 时,语句 fi > 0 必须为真。

如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

5 6 1 5
1 2 1
2 3 1
3 5 1
1 4 1
4 3 0
4 5 1

输出 #1

2
3 3
3 8
3 4
4 4
0 5
4 9

注意

第二个示例案例的插图。饱和的边缘标记为黑色,而 gi = 0 的边缘标记为虚线。边上的整数是该边在输入列表中的索引。