#2962. 哈密顿回路?通路!

哈密顿回路?通路!

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你瞄了一眼今天的 "T3T3":

给定 N 个点的带权无向完全图,求最短的哈密顿回路的长度。

看了下数据范围,你自信满满地写了个状压 dp,然后果断跳去 T4T4,甚至样例都没有测。 “代码不可能会写错的!” 真正的 oier 永远不对拍!你从来没有怀疑过自己的代码能力。

比赛的最后 1 min,你重新读了下题,才发现要求的是最短的哈密顿通路的长度。 “没有时间重写了,从求得的哈密顿回路里贪心丢掉最长的一条边。能骗多少骗多少吧。” -- 这次脑子只转了 1 秒钟,你马上做出了一个最正确的决策。

然后碰上了面对选手代码精心构造数据的出题人,铁了心想要 hack 掉你的贪心做法,他希望能构造这样的数据:

给定 NNLL,要求构造一个 NN 个点的带权完全无向图 GG,满足:

  1. 边权范围在 [1,L][1, L];
  2. 设该图上最短的哈密顿通路的长度为 h(G)h(G),而你的错解给出的最优答案(如果存在多种哈密顿回路,运气不错的你总能找到一个去掉最长边后答案最小的结果)是 f(G)f(G),需要满足 f(G)h(G)>=L/2f(G) - h(G) >= \lfloor{L/2}\rfloor

注: 哈密顿回路是指通过图中所有顶点一次且仅一次的回路; 哈密顿通路是指通过图中所有顶点一次且仅一次的通路。

输入格式

N LN\ L

输出格式

如果无论如何都无法构造满足要求的带权完全图,输出一行 "-1"。

否则输出 NNN * N 的边权矩阵,满足 di,j=dj,id_{i,j} = d_{j,i}di,i=0d_{i,i} = 0

0 d1,2 ... d1,n0\ d_{1,2}\ ...\ d_{1,n} d2,1 0 ... d2,nd_{2,1}\ 0\ ...\ d_{2,n} ... dn,1 dn,2 ... 0d_{n,1}\ d_{n,2}\ ...\ 0

样例

样例输入

6 1000

样例输出

0 174 325  60 839 248
174   0 437 398 965 806
325 437   0 658 985 969
 60 398 658   0 319 100
839 965 985 319   0 149
248 806 969 100 149   0

提示

样例 1 解释:

给定图中哈密顿通路的长度是 920,通过的节点分别是 2->1->0->3->5->4; 拥有最长边的最短的哈密顿回路0->2->1->3->4->5->0,其中最长边是 2->1: 437去掉最长边后得到的伪哈密顿通路的长度是 1439

数据范围:

  • 约 14 pts:N=6N = 6
  • 约 32 pts:L<=20L <= 20
  • 对于 100%100\% 的数据:6<=N<=14, 10<=L<=1096 <= N <= 14,\ 10 <= L <= 10^9

第二届小云雀杯决赛(提高组)

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-5-3 10:20
结束于
2023-5-3 12:50
持续时间
2.5 小时
主持人
参赛人数
144