#P4986. [2017年湖南省队集训]MiniumCut

    ID: 924 传统题 1000ms 256MiB 尝试: 10 已通过: 6 难度: 6 上传者: 标签>难度分类提高图论最小割Kruskal数据结构普通并查集枚举与搜索深度优先搜索构造与建模图构造CF2100

[2017年湖南省队集训]MiniumCut

最小割还原图

题目描述

给定一张 nn 个顶点的图的两两最小割值。请还原一张满足这些值的连通无向图。对于两个不同顶点,它们的最小割值是分开这两点所需割去的边的最小权值和。

输入格式

第一行一个正整数 nn,满足 n≤100n\le100。顶点编号为 11 至 nn。

接下来 nn 行每行 nn 个非负整数。第 ii 行第 jj 列的数 vijv_{ij} 表示指定的两点最小割值,满足 vij≤105v_{ij}\le10^5。保证 vii=0v_{ii}=0。

输出格式

无解时输出一行 -1。有解时输出任意一个可行图,第一行给出边数 mm,其中 m≤n(n−1)/2m\le n(n-1)/2。接下来 mm 行,每行三个整数 u,v,zu,v,z,表示一条连接 u,vu,v、权值为 zz 的无向边。1≤u,v≤n1\le u,v\le n,0<z≤1090<z\le10^9。输出的图必须连通。

样例

3
0 2 2 
2 0 2
2 2 0
2
2 3 2
1 3 2