求助一个构造题
  • 板块学术版
  • 楼主Terraria
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/7/26 11:59
  • 上次更新2023/11/4 13:17:01
查看原帖
求助一个构造题
289275
Terraria楼主2021/7/26 11:59

好几天前就想到的 idea,到现在还是不会做/kk

如下:

已知 nn,求构造 n1n-1 条有权双向边,使得任意两个顶点可以互相到达,且两两结点之间的最短距离为 1,2,3,,n(n1)21,2,3,\cdots,\dfrac{n(n-1)}{2} 的一个排列。

目前手算推出 n=2,3,4,6n=2,3,4,6 时有解,求大佬提供一个判断是否有解的充分必要条件和具体的构造方案,谢谢!

2021/7/26 11:59
加载中...