![](data:image/svg+xml;charset=utf-8,<svg width="640" height="640" style="background-color:%2344badc;font-family:Nunito,sans-serif" viewBox="0 0 100 100" preserveAspectRatio="xMidYMid meet" xmlns="http://www.w3.org/2000/svg">
<text font-size="30" x="50%" y="50%" dy="5" fill="white" dominant-baseline="middle" text-anchor="middle">Sl</text>
</svg>)
#algorithms
#complexity
Если в постановке задачи mincost maxflow сказать, что стоимость считается не пропорционально потоку через ребро, а будет константной, если по ребру течёт хоть какой-то поток и нулем в противном случае, то такая задача, в отличие от исходной, не будет иметь полиномиального решения и вовсем будет NP-complete:
https://codeforces.com/blog/entry/51223?#comment-351053
#complexity
Если в постановке задачи mincost maxflow сказать, что стоимость считается не пропорционально потоку через ребро, а будет константной, если по ребру течёт хоть какой-то поток и нулем в противном случае, то такая задача, в отличие от исходной, не будет иметь полиномиального решения и вовсем будет NP-complete:
https://codeforces.com/blog/entry/51223?#comment-351053