关于此题无正圈的证明
查看原帖
关于此题无正圈的证明
484910
SwordDance楼主2024/7/26 23:25

rt,一开始我也想不明白为什么一定没有正圈,尝试构造一组正圈的时候发现不可行。

设四个可能构成正圈的点依次设为A、B、C、D。显然,必然有两个点在源点侧,两个在汇点侧,不妨设源点侧的点为A、B。

那么A->C边权为a[A]-kb[C],C->B边权为kb[C]-a[B],B->D的边权为a[B]-kb[D],D->A的边权为kb[D]-a[A],我们惊奇地发现:四条边加起来的和恰好为0!

对于更多点可能构成正圈的情况同理。所以原图一定不存在正圈。很遗憾没能看到有题解证明这点,故在讨论区发表,希望被淹下去的时候有人能补档。

2024/7/26 23:25
加载中...