路径长度为 $l=m/\deg(1)$，则最大流为 $f=\lfloor\sum_ec_e/l\rfloor$，现在问题变成了若干个大小相同的可重集合，每次给一个数加 $1$，使得每个集合的最小值之和 $=f$。由于代价是凸的，直接贪心即可。时间复杂度：$O(m\log m)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.