BZPRO
#4986. MiniumCut
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
从前有张图。图里n个顶点两两之间有N^2种最小割。告诉你这N^2个最小割。还原出这张图。
输入格式
第一行一个正整数n，表示图的顶点数。
接下来n行每行N个非负整数，第i行第j列的数表示第i个点与第j个点的最小割。
点的编号从1开始。
Vi<=10^5,n<=100
保证vii=0。
输出格式
第一行一个整数m，表示图的边数。
接下来每行三个整数u,v,z。
表示从“到”存在一条权值为z的边。
l<=u,v<=N
0<Z<=10^9。
m<=n*(n-l)/2。
请注意你给出的图要求联通。
如果无解请输出-l。
若有多解则输出任意一组解。
样例
样例输入
3
0 2 2
2 0 2
2 2 0
样例输出
2
2 3 2
1 3 2
数据范围与提示
请不要提交！
BZPRO