#P4986. [2017年湖南省队集训]MiniumCut
[2017年湖南省队集训]MiniumCut
最小割还原图
题目描述
给定一张 个顶点的图的两两最小割值。请还原一张满足这些值的连通无向图。对于两个不同顶点,它们的最小割值是分开这两点所需割去的边的最小权值和。
输入格式
第一行一个正整数 ,满足 。顶点编号为 至 。
接下来 行每行 个非负整数。第 行第 列的数 表示指定的两点最小割值,满足 。保证 。
输出格式
无解时输出一行 -1。有解时输出任意一个可行图,第一行给出边数 ,其中 。接下来 行,每行三个整数 ,表示一条连接 、权值为 的无向边。,。输出的图必须连通。
样例
3
0 2 2
2 0 2
2 2 0
2
2 3 2
1 3 2