#46. 城市规划
城市规划
题目描述
zjn 所在的城市里的路口非常多,导致道路非常混乱,所以市政府准备进行一次道路规划,使得城市道路变得简洁清晰。
市政府希望将整个城市的道路规划成一棵树,也就是说如果城市共有 个路口,那么最后只留下 条双向道路使得所有路口都连通。
同时,市政府认为对于一个路口 来说,所有和它直接相连的道路长度的平均值,就是这个路口的视野好坏程度,市政府会选择视野最好的路口作为中心路口
为了加快规划进度,市政府向所有市民征集规划方案,zjn 自然也想为城市建设处一份力,于是他仔仔细细的走遍了城市的每一条道路,列出了所有信息。
zjn 每次会给出一个规划方案,这个方案是一张 行 列的表格 。
其中 表示 zjn 的规划中第 个路口到第 个路口的最短距离为
当然这 只是表示第 个路口到第 个路口的最短距离为 ,并不一定表示第 个路口和第 个路口一定存在一条双向道路连接。
zjn 列出了好多种他想到的规划方案,但是他不确定这些方案是否正确。
现在他希望你来帮他判断一下,某个方案是否足够正确,如果正确则请你再告诉他中心路口是哪个路口,如果存在多个视野程度一样的路口,则选择编号小的路口作为中心路口。
输入格式
输入第一行包含一个正整数 表示共有 组测试数据 对于每组测试数据: 第一行包含一个正整数 接下来 行每行包含 个整数表示道路长度
输出格式
对于每组测试数据,如果规划方案是清晰的,则输出 Yes
否则输出 No
如果规划方案是清晰的,则再输出中心路口的编号。
数据范围
对于 的数据,
对于 的数据,
对于 的数据,
对于所有数据保证
样例输入
样例输出
样例解释
对于第一组样例可以发现,城市中的道路为 存在一条长度为 的双向道路, 存在一条长度为 的双向道路, 的最短距离为 ,那么这个规划就是正确的 其中视野最好的路口是
对于第二组样例, 存在自环,所以不满足条件
相关
在下列比赛中: