如何证明贪心的正确性?
查看原帖
如何证明贪心的正确性?
518899
FXT1110011010OI楼主2024/3/27 16:16

对于题目的第二问,题解中有一贪心做法:从大到小枚举每条边,如果可以作为最小割的割边(满流),则答案加一,然后删去这条边。

假设可以作为最小割的割边的边中,最长边的长度为 xx,另一条边的长度为 yy。能不能构造一种图,使得 xx 所在最小割的割边数量大于 yy 所在最小割的割边数量?

如果能构造,则贪心做法是错误的;如果不能构造,为什么?

2024/3/27 16:16
加载中...