5483: Design Tutorial: Inverse the Problem

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:4 通过:4

题目描述

D、 设计教程:解决问题
有一种简单的方法可以从一个叫做“逆问题”的旧任务中获得一个新任务:我们给出原始任务的输出,并要求生成一个输入,这样原始问题的解决方案将生成我们提供的输出。Topcoder Open 2014第2C轮的艰巨任务InverseRMQ就是一个很好的例子。
现在让我们用这种方式创建一个任务。我们将使用该任务:您将得到一棵树,请计算其任意一对节点之间的距离。是的,这很容易,但逆版本有点难:给你一个n×n距离矩阵。确定它是否是加权树的距离矩阵(所有权重必须为正整数)。
输入
第一行包含整数n(1≤n≤2000)−该图中的节点数。
然后,接下来的n条线分别包含n个整数di,j(0≤di,j≤109)−节点i和节点j之间的距离。
输出
如果存在这样的树,则输出“是”,否则输出“否”。
示例
Input
3
0 2 7
2 0 9
7 9 0
Output
YES
Input
3
1 2 7
2 0 9
7 9 0
Output
NO
Input
3
0 2 2
7 0 9
7 9 0
Output
NO
Input
3
0 1 1
1 0 1
1 1 0
Output
NO
Input
2
0 0
0 0
Output
NO

输入格式

第一行包含整数n(1≤n≤2000)−该图中的节点数。
然后,接下来的n条线分别包含n个整数di,j(0≤di,j≤109)−节点i和节点j之间的距离。

输出格式

如果存在这样的树,则输出“是”,否则输出“否”。

输入样例 复制

3
0 2 7
2 0 9
7 9 0

输出样例 复制

YES

数据范围与提示

在第一个示例中,存在所需的树。它具有权重为2的节点1和2之间的一条边,权重为7的节点1与3之间的另一条边。

在第二个示例中,这是不可能的,因为d1,1应该是0,但它是1。

在第三个例子中,这是不可能的,因为d1,2应该等于d2,1。