Picnic
[USACO06DEC] Cow Picnic S
P2853 [USACO06DEC] Cow Picnic S 逆向思维 如果顺着题目走,不大好做。 考虑该题要求的是可以供所有奶牛到达的牧场,那么不如从奶牛所在的牧场下手 即对每个奶牛所在的牧场 \(DFS\),对所有到达点标记。 那么显然当一个点的标记等于 \(k\) 时,说明该牧场是合适的。 ......
picnic planning证明
首先最终的答案一定包含最开始的T条边,不然的话,我们选择这T条边中没被包含的任意一条边,把它加入现有的生成树 由于这T条边连接的是不同的连通块,所以加入这条边后生成树会形成一个环,而且这个环除了这一条边不包含其他任何一条这T条边中的一边 又因为这T条边是最小的T条边,我们选择这个环上从1出发的不是这 ......