所以最大费用最大流不是多项式可解的
by 小粉兔 @ 2020-08-21 14:33:10
本题中的最大费用最大流是不存在环的呀。
by code_hunter @ 2021-06-09 11:01:35
@[searchstar](/user/92652) 最大费用最大流你每次都求了最长路 ， 跑了spfa ， 这是在假设没有正环的条件下进行的，依赖于 spfa 最长路的正确性，所以只能在没有正环的情况跑。
有正环的最大费用最大流是 多项式可解的，但是由于流函数的定义，是允许一个环“凭空增流的” ， 这也符合流函数定义，就像一个环的最小路径覆盖用网络流求出来是 0 一样
by ღꦿ࿐ @ 2022-05-09 14:50:41
@[ღꦿ࿐](/user/161697) 有正环的最大费用最大流是多项式可解的？那什么情况下最大费用最大流不是多项式可解的？
by searchstar @ 2022-08-04 17:19:26
@[searchstar](/user/92652) 按照流函数的定义，是可解的
见 [此处](https://www.luogu.com.cn/problem/P7173)
只是这个时候它和最长路之间就没有约化关系了
\*DAG的最长路是多项式可解，但是谁会用费用流啊（（
by ღꦿ࿐ @ 2022-08-04 19:04:24
@[ღꦿ࿐](/user/161697) 懂了。也就是说，如果用最大费用最大流来解最长路问题的话，求出的其实是一条从起点到终点的一条路径以及其他独立的环是吧？
已经退役很久了，现在才看到（
by searchstar @ 2022-08-24 11:34:26