建议加固题面

P8857 [POI2002] 滑雪者

kdx_dy @ 2024-04-03 15:58:54

@Yizhixiaoyun 理论上来说，边数可以达到惊人的 n*n ，这样空间会炸，建议题面说明 \sum\limits_{i=1}^{n}k_i 的范围。

by kdx_dy @ 2024-04-03 15:59:17

@Yizhixiaoyun

by kdx_dy @ 2024-04-03 16:04:10

经实测， \sum\limits_{i=1}^{n}k_i \le 9000 。

by kdx_dy @ 2024-04-03 16:04:35

@Alex_Wei

by 0000pnc @ 2024-04-03 22:01:23

@NFLS_DingYi 平面图的边数 \le 3n-6

by forgotmyhandle @ 2024-04-04 00:03:23

@0000pnc 这题哪里保证给的一定是平面图了？

5
4 1 2 3 4
3 3 4 5
2 4 5
1 5

直接给一张完全图，每条边由编号小的向编号大的连，边数就是平方级别的。

by forgotmyhandle @ 2024-04-04 00:04:35

上面那个数据写错了 应该是

5
4 2 3 4 5
3 3 4 5
2 4 5
1 5

by Skeleton_Huo @ 2024-04-04 20:46:26

@NFLS_DingYi @forgotmyhandle 翻译的确有问题，可以来这里看一下原题面。

Ski tracks may cross only on clearings and do not run through tunnels nor on bridges.

by forgotmyhandle @ 2024-04-04 21:20:30

@Skeleton_Huo 原来是这样的吗，那建议在题目里加一句保证给出的是平面图或者直接给出 \sum k 的范围。

by tzl_Dedicatus545 @ 2024-07-18 19:28:39

@chen_zhe 建议加上图是平面图的限制。。。

|