abc397g
首先考虑二分答案，然后你建出分层图。\((u,i)\) 连接 \((u,i+1),(v,i+1)\) 流量都为 \(+\infty\)；然后 \((u,i)\) 也要连接 \((v,i)\)，流量为 \(1\)。然后源汇连什么是显然的，最后合法条件就是最小割 \(\le k\)。
代码
首先考虑二分答案，然后你建出分层图。\((u,i)\) 连接 \((u,i+1),(v,i+1)\) 流量都为 \(+\infty\)；然后 \((u,i)\) 也要连接 \((v,i)\)，流量为 \(1\)。然后源汇连什么是显然的，最后合法条件就是最小割 \(\le k\)。
代码