ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
5483: Design Tutorial: Inverse the Problem
内存限制:256 MB
时间限制:2 S
题面:传统
评测方式:文本比较
上传者:
提交:4
通过:4
提交
提交记录
统计
Web Board
题目描述
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。
分类标签
472D
1900
trees
dsu