#P18486. Minimum Cost Flow²

Minimum Cost Flow²

Minimum Cost Flow²

通常的最小费用流中,若一条边的费用系数为 cc、通过的流量为 ff,使用它的费用为 cfcf,即费用与流量成线性关系。本题研究另一种费用函数:边的费用与流量的平方成正比。你要将 11 单位流量从源点送到汇点,使总费用最小。

给定一个有 nn 个点、mm 条边的有向图,点编号为 1,2,…,n1,2,\ldots,n。点 11 是源点,点 nn 是汇点。边 ee 的费用系数为 cec_e。你需要为每条边选择一个实数 fef_e,表示该边上的流量,满足:

  • 源点的净流出量为 11:$\displaystyle\sum_{e\in\operatorname{out}(1)} f_e-\sum_{e\in\operatorname{in}(1)}f_e=1$。
  • 每个中间点 1<u<n1<u<n 的净流出量为 00:$\displaystyle\sum_{e\in\operatorname{out}(u)} f_e-\sum_{e\in\operatorname{in}(u)}f_e=0$。
  • 在所有满足上述条件的流量中,使总费用 ∑ecefe2\displaystyle\sum_e c_ef_e^2 最小。

这里 out⁡(u)\operatorname{out}(u)、in⁡(u)\operatorname{in}(u) 分别表示从 uu 出发、进入 uu 的边集。边没有容量限制,流量的大小没有上界。流量可以为负数,负流量表示流沿着该有向边的反方向通过。

求最小总费用,并将其对 998 244 353998\,244\,353 取模输出。在本题条件下,最优费用一定是有理数,下面给出取模的精确定义。

输入格式

第一行一个整数 tt(1≤t≤1001\le t\le100),表示测试用例数。

每个测试用例先输入两个整数 n,mn,m(2≤n≤1002\le n\le100,1≤m≤3001\le m\le300)。随后 mm 行,每行三个整数 u,v,cu,v,c(1≤u,v≤n1\le u,v\le n,1≤c<998 244 3531\le c<998\,244\,353),表示一条从 uu 到 vv、费用系数为 cc 的边。

没有自环、重边或反平行边。也就是说,一个无序点对最多对应一条边。忽略方向后,图连通。

同一个输入文件中,所有测试用例的 n+mn+m 之和不超过 400400。

设 P=998 244 353P=998\,244\,353。数据保证至少存在一个最优流,使每条边的流量都能写成整数分式 p/qp/q,且 q≢0(modP)q\not\equiv0\pmod P。

输出格式

每个测试用例输出一行,一个整数。

将最小总费用表示成既约分数 p/qp/q。可以证明 q≢0(modP)q\not\equiv0\pmod P。输出任意满足

−231≤x<231,xq≡p(modP)-2^{31}\le x<2^{31},\qquad xq\equiv p\pmod P

的整数 xx。因此负数同余表示也可以是合法答案;不必只输出 [0,P−1][0,P-1] 中的表示。

原样例

输入:

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