社区讨论

【求问】对于特殊性质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:对于所有 1jk1 \leq j \leq k,均有 cj=0c_j = 0 且均存在 1in1 \leq i \leq n 满足 aj,i=0a_{j,i} = 0
一想,cj=0c_j = 0 说明 C 国对每个乡镇进行城市化改造的费用都为 00,所以每个乡镇都可以随意开发。 而 aj,i=0a_{j,i} = 0 说明在它与每座城市间建造一条道路的费用也都为 00。由于题目只要求 “任意两座城市都能通过若干条道路相互到达” ,是不是说明:
只要将任意一个乡镇花费 00 的代价改造为城市,再与其他每一个城市花费 00 的代价全部连通,就可以使得任意两座城市都能通过若干条道路相互到达,总代价为 00
例如下面的样例,这是满足特殊性质A的(如果我没有理解错题意的话)
CPP
4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
0 0 0 0 0
0 0 0 0 0
自己干瞪眼都看得出来,必须是 00 吧?我去题解里抓了一篇跑了一下也是 00。(澄清:我只是在Dev上验证了一下,没有抄题解的意思)
但是,我觉得这个看似无懈可击的写法 (偷鸡),却没有一个人跟我讨论过,某交流群了没有一个人说过,不知道是大家都去想正解了看不起偷鸡还是怎么。而且洛谷用这个方法也只有 4pts4pts,根本没有预期的 4040 分。
谁能给我解答一下?谢谢。

回复

21 条回复,欢迎继续交流。

正在加载回复...