在 Grad-ProbAsk 版看到的问题。
给定 n 篇 paper 和 m 个 reviewer，
Reviewer 不是每篇 paper 都可以审，
可以审查的关系用一集合
R = {(reviewer, paper) | 此 reviewer 可以审该 paper} 表示。
Chairman 要指派 paper 给 reviewer，每个 reviewer 最多
只能审 k1 篇 paper。
objective: 最大化被 k2 个 reviewer 审过的 paper 数量
看起来很像是 network flow，但是 objective 该怎么用 network flow 表示？
如果有其他 min-cost flow/linear programming 的方法也可以。

paper 跟 reviewer 建法一样, 求完最大流看 paper 的边的剩余容量, 这样可行吗?

感觉这个目标式不能用LP解另外回一楼 是否会有求完最大流但paper没被审到k2次的

因为 paper 跟源点 (或汇点) 每条边上限 k2, 这样应该就不存在可行的指派法了

不太懂为何会没有可行解？

上限 k2 代表 paper 最多被 k2 个人审但是题目是要求被 k2 个人审的 paper 数量最多

喔喔, 所以是要求被合法指派的 paper 数量最多?不知有没有影响, 那 paper 可以被审超过 k2 次吗啊没看清楚 objective 抱歉

paper 审超过 k2 次是没差啊 但是我不觉得这样会比较容易.

直接套边有上下界限制的网络流就好了吧