#P18515. Flow 2
Flow 2
Flow 2
Little Cyan Fish 和他的队友、北京大学的 Qingyu Xiao 正在上算法课。他们正在阅读 Maximum Flow and Minimum-Cost Flow in Almost-Linear Time 与 All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time。Little Cyan Fish 对最大流很感兴趣,希望你帮助解决一个相关问题。先回顾几个基本概念。
没有重边、没有自环的无向图 G=(V,E) 称为简单图。所有边的容量均为1,即图中的边都没有权值。
对两个不同的顶点 s,t,分别把它们称为源点和汇点。流为边上非负流量的分配(沿所使用的方向记作 f_uv),需要满足:
- 容量限制:每条边的流量不超过1,即 0≤f_uv≤1;
- 流量守恒:除 s,t 以外,任意顶点的流入量等于流出量,即
流的值是从源点送到汇点的流量,形式上为
$$|f|=\sum_{v:(s,v)\in E}f_{sv}=\sum_{u:(u,t)\in E}f_{ut}.$$所有可行流中最大的流值记为 maxflow(s,t)。特别定义 maxflow(u,u)=0。无向边按通常的无向单位容量最大流理解,沿相反方向的流可以抵消。
现在,给出一张有 n 个顶点的无向简单图 G,顶点编号为1到n,计算矩阵 A=F(G),其中 A_uv=maxflow(u,v),是课程中的一道作业。Little Cyan Fish 认为这很直接,于是想研究逆问题:给定矩阵 A,构造一个无向简单图 G,使 F(G)=A。
一般的矩阵很难处理,所以本题保证矩阵的每个元素只可能是0、1、2、3。你能构造这样的图,或者判断不存在吗?
输入格式
第一行一个整数 T(1≤T≤1000),表示测试用例个数。
对每个测试用例:
- 第一行一个整数 n(1≤n≤300);
- 接下来 n 行,每行 n 个整数,第 i 行描述 A_i1,…,A_in;
- 保证所有元素满足0≤A_ij≤3。
保证同一输入文件中所有测试用例的 n² 之和不超过 9×10^6。输入不保证对称、对角为0或者存在对应的图。
输出格式
对每个测试用例,若不存在满足 F(G)=A 的图,输出一行 No。
否则先输出一行 Yes,下一行输出所用边数 m,随后 m 行各输出两个整数 x,y,表示一条连接顶点 x,y 的无向边。输出图必须是无向简单图,不能有重边或自环,顶点仍为1到n。
若有多种合法方案,输出任意一种。
完整原样例
输入:
4
4
0 3 2 2
3 0 2 2
2 2 0 2
2 2 2 0
8
0 2 2 0 0 1 1 1
2 0 2 0 0 1 1 1
2 2 0 0 0 1 1 1
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
1 1 1 0 0 0 2 2
1 1 1 0 0 2 0 2
1 1 1 0 0 2 2 0
3
0 1 2
1 2 3
2 3 1
12
0 2 2 2 2 2 2 2 2 1 1 1
2 0 2 2 2 2 2 2 2 1 1 1
2 2 0 2 2 2 2 2 2 1 1 1
2 2 2 0 2 2 2 2 2 1 1 1
2 2 2 2 0 2 2 2 2 1 1 1
2 2 2 2 2 0 2 2 2 1 1 1
2 2 2 2 2 2 0 2 2 1 1 1
2 2 2 2 2 2 2 0 2 1 1 1
2 2 2 2 2 2 2 2 0 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0
输出(其中一种方案):
Yes
5
1 2
3 1
3 2
4 1
4 2
Yes
8
1 2
2 3
3 1
6 7
7 8
8 6
1 6
4 5
No
Yes
12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 1
1 10
10 11
11 12
原样例说明
第一个测试用例的一种可行图如下。

以 A_12=3 为例,下面的图展示了流值3的最大流,满足 maxflow(1,2)=3。

第二个测试用例的一种可行图如下。

第三个测试用例显然没有满足所有 A_uu=0,因此不存在对应图。