关于题目描述的疑惑

P2272 [ZJOI2007] 最大半连通子图

LaDeX @ 2024-12-31 15:30:26

观察题目对半连通子图 的描述:

G'=(V',E')

可以发现子图是包含边集的,这是否意味着边集不同的子图算作不同的种类统计入答案呢。

但是我测试了两篇题解(第四篇和第五篇),输入为三个点的完全图:

3 6 100000000
1 2
2 1
1 3
3 1
2 3
3 2

但是输出的第二行都是 1,可是很显然并不需要选择所有的边保证半连通,方案肯定不止一种,这是否意味着题目描述有问题,应该明确相同点集不同边集的子图也算相同呢。


by Milky_Cat @ 2024-12-31 15:31:39

这都卷?


by WrongAnswer_90 @ 2024-12-31 16:01:31

@LaDeX 题目第二段

G'=\left(V',E'\right) 满足 V'\subseteq VE'E 中所有跟 V' 有关的边


by LaDeX @ 2024-12-31 16:04:04

@WrongAnswer_90 thx


|