路径长度为 $l=m/\deg(1)$，则最大流为 $f=\lfloor\sum_ec_e/l\rfloor$，现在问题变成了若干个大小相同的可重集合，每次给一个数加 $1$，使得每个集合的最小值之和 $=f$。由于代价是凸的，直接贪心即可。时间复杂度：$O(m\log m)$。
QOJ.ac
QOJ
Discussion #218 for Problem #5042. Flow
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:16:31
Last updated: 2025-12-13 00:16:35
题解
Comments
No comments yet.