社区讨论
【求问】对于特殊性质A是否可以直接输出0?
P14362[CSP-S 2025] 道路修复参与者 10已保存回复 21
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 21 条
- 当前快照
- 1 份
- 快照标识符
- @mhiya5el
- 此快照首次捕获于
- 2025/11/03 17:41 4 个月前
- 此快照最后确认于
- 2025/11/03 17:45 4 个月前
声明:本人只是一个初一的彩笔,人人都知道这题用Kruskal但我脑子不好使由于种种原因无法场切,所以求求勿喷
考场上看到特殊性质A
特殊性质 A:对于所有 ,均有 且均存在 满足 。
一想, 说明 C 国对每个乡镇进行城市化改造的费用都为 ,所以每个乡镇都可以随意开发。 而 说明在它与每座城市间建造一条道路的费用也都为 。由于题目只要求 “任意两座城市都能通过若干条道路相互到达” ,是不是说明:
只要将任意一个乡镇花费 的代价改造为城市,再与其他每一个城市花费 的代价全部连通,就可以使得任意两座城市都能通过若干条道路相互到达,总代价为 ?
例如下面的样例,这是满足特殊性质A的(如果我没有理解错题意的话)
CPP4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
0 0 0 0 0
0 0 0 0 0
自己干瞪眼都看得出来,必须是 吧?我去题解里抓了一篇跑了一下也是 。(澄清:我只是在Dev上验证了一下,没有抄题解的意思)
但是,我觉得这个看似无懈可击的写法 (偷鸡),却没有一个人跟我讨论过,某交流群了没有一个人说过,不知道是大家都去想正解了看不起偷鸡还是怎么。而且洛谷用这个方法也只有 ,根本没有预期的 分。
谁能给我解答一下?谢谢。
回复
共 21 条回复,欢迎继续交流。
正在加载回复...