有N个机器（1…N），有M（1…M）件工作需要完成。并不是每个机器都能完成所有的工作，也就是说，每个机器只能完成某一些的工作。如果在第i台机器上完成t件工作，那么需要的花费是 cost[i] * t*t。
现在告诉你每台机器可以完成的工作编号，以及每台机器的cost。请你计算出完成所有的工作需要的最小的代价
这题如果话费是cost[i]*t的话，那么,如果i能完成j号任务，那么就连i到j的边，容量为1，费用为cost[i] 然后加入源点s，s到每个机器的流量为inf，每台机器到汇点t的容量为1,最后求s到t的最小费用最大流就可以了。
可是费用是cost[i]*t*t
t*t=1+3+5+7+9+……+（2*t-1)
如果第i台机器能够完成k项任务那么就把他分成k个点 从源点到 Dik的费用定义为 (2*k-1)，容量为1，后面的建图方式如上
最后还是求s到t的最小费用最大流即可
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。