#P18486. Minimum Cost Flow²
Minimum Cost Flow²
Minimum Cost Flow²
通常的最小费用流中,若一条边的费用系数为 、通过的流量为 ,使用它的费用为 ,即费用与流量成线性关系。本题研究另一种费用函数:边的费用与流量的平方成正比。你要将 单位流量从源点送到汇点,使总费用最小。
给定一个有 个点、 条边的有向图,点编号为 。点 是源点,点 是汇点。边 的费用系数为 。你需要为每条边选择一个实数 ,表示该边上的流量,满足:
- 源点的净流出量为 :$\displaystyle\sum_{e\in\operatorname{out}(1)} f_e-\sum_{e\in\operatorname{in}(1)}f_e=1$。
- 每个中间点 的净流出量为 :$\displaystyle\sum_{e\in\operatorname{out}(u)} f_e-\sum_{e\in\operatorname{in}(u)}f_e=0$。
- 在所有满足上述条件的流量中,使总费用 最小。
这里 、 分别表示从 出发、进入 的边集。边没有容量限制,流量的大小没有上界。流量可以为负数,负流量表示流沿着该有向边的反方向通过。
求最小总费用,并将其对 取模输出。在本题条件下,最优费用一定是有理数,下面给出取模的精确定义。
输入格式
第一行一个整数 (),表示测试用例数。
每个测试用例先输入两个整数 (,)。随后 行,每行三个整数 (,),表示一条从 到 、费用系数为 的边。
没有自环、重边或反平行边。也就是说,一个无序点对最多对应一条边。忽略方向后,图连通。
同一个输入文件中,所有测试用例的 之和不超过 。
设 。数据保证至少存在一个最优流,使每条边的流量都能写成整数分式 ,且 。
输出格式
每个测试用例输出一行,一个整数。
将最小总费用表示成既约分数 。可以证明 。输出任意满足
的整数 。因此负数同余表示也可以是合法答案;不必只输出 中的表示。
原样例
输入:
4
4 4
1 2 1
2 4 1
1 3 1
3 4 1
3 3
1 2 1
1 3 1
2 3 1
5 6
1 2 1
2 3 3
2 4 1
3 4 1
3 5 1
1 5 8
4 5
1 2 1
1 3 2
2 3 1
3 4 1
4 2 8
输出:
1
665496236
713031683
614304219