今天我读书的时候发现一道练习题很有趣:
它给出了一个计算网络最大流的算法(假的),大意是只寻找增广路,不连反向边,一直增广无法增广为止。可以证明求出的不一定是最大流。
但是它提出了这样一个命题:
在任意网络上,不论何种情况(不管算法怎样遍历),总有一个常数 b≥1,使得上述算法算出的最大流一定大于等于真正的最大流的 b1。
要求证实或证伪。
于是我画了一个熟悉的图:
不难看出这个图里无论把 999 改到多大,最后计算出的假最大流一定大于真最大流的 21,但是蒟蒻想不出更多的思路了,书里也没有答案qwq
求问大佬们qwq