有一种简单的方法可以从旧任务中获取新任务,称为“逆问题”:我们给出原始任务的输出,并要求生成输入,这样原始问题的解决方案将产生我们提供的输出。 Topcoder Open 2014 Round 2C 的硬任务 InverseRMQ 就是一个很好的例子。
现在让我们以这种方式创建一个任务。我们将使用以下任务:给你一棵树,请计算其任意一对节点之间的距离。是的,这很简单,但逆版本有点难:给你一个 n × n 距离矩阵。判断是否是带权树的距离矩阵(所有权重必须为正整数)。
输入
第一行包含一个整数 n (1 ≤ n ≤ 2000) — 该图中的节点数。
接下来的 n 行每行包含 n 个整数 di, j (0 ≤ di, j ≤ 109) — 节点 i 和节点 j 之间的距离。
输出
如果存在这样的树,则输出“YES”,否则输出“NO”。
示例
输入 #1
3 0 2 7 2 0 9 7 9 0
输出 #1
YES
输入 #2
3 1 2 7 2 0 9 7 9 0
输出 #2
NO
输入 #3
3 0 2 2 7 0 9 7 9 0
输出 #3
NO
输入#4
3 0 1 1 1 0 1 1 1 0
输出#4
NO
输入 #5
2 0 0 0 0
输出 #5
NO
注意
在第一个示例中,存在所需的树。它在节点 1 和 2 之间有一条边,权重为 2,在节点 1 和 3 之间有另一条边,权重为 7。
在第二个例子中,这是不可能的,因为 d1, 1 应该是 0,但它是 1。
在第三个示例中,这是不可能的,因为 d1, 2 应等于 d2, 1。