0

这是参考“图形存在”问题 - http://acm.mipt.ru/judge/problems.pl?problem=110。有人可以解释为什么示例 1 中没有树但示例 2 中有树吗？在这两个示例中，顶点 0、1、2 和 3 相互连接。以下是问题陈述和示例供您参考：

你会得到一个图表中的距离矩阵。
您应该检查此图是否可能是一棵树或一组树（森林）。
边长为 0 或正整数。

输入：第一行包含顶点数 N。
接下来的 N 行包含矩阵（仅矩阵的左下三角形）。
距离 -1 对应于无限距离。

输出：输出YES或NO。如果是，那么下一行应该包含边列表
树（具有给定距离矩阵的任何树（森林））。
每条边都由其末端的两个标识符编码。
顶点标识符是数字 0、1、...、N-1。

输入#1
4
0
1 0
1 1 0
1 1 1 0

输出#1
不

输入#2
5
0
1 0
2 1 0
3 2 1 0
-1 -1 -1 -1 0

输出#2
是的
0 1
1 2
2 3
4

1 回答 1

1

这个问题不是很好地从它的俄语原文翻译过来的。

给定的矩阵不是人们可能得出的结论的图中边的矩阵，而是一个距离矩阵。每条边的权重可能为 1，但我不完全确定是否有非负权重。必须检查矩阵是否可以通过一棵树或一片森林来实现。

也就是说，在第一个示例中所有顶点都是连接的，但第二个示例可以实现图形如下所示：

    Example 2:
    (0) - (1) - (2) - (3)  (4)

示例 1 中的图形是

    Example 1:
    (0) - (1) - (2) - (3)
     |_____|_____|     |     
     |     |___________|
     |_________________|
于 2012-09-29T14:16:12.760 回答