← 返回题目列表

Codeforces · 472/D

D. 设计教程:反演问题

中文机器翻译题面 查看原题

有一种简单的方法可以从旧任务中获取新任务,称为“逆问题”:我们给出原始任务的输出,并要求生成输入,这样原始问题的解决方案将产生我们提供的输出。 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。