poj2516:Minimum Cost

题目链接

poj2516

这道毒瘤费用流……

对不起打扰了

题解

输入格式如图………

二分图建图方式简单粗暴……输入格式比较毒瘤

对于\(k\)个问题我们可以跑k次费用流求得

没错,动态建图+多次费用流,每次费用流求出的的是对于这个物品的最小花费,那么对于所有物品的最小花费就是\(\sum_{i=1}^kmincost_i\),直接zkw就好了。

一旦有一次求出的最大流不等于该中商品的需求量之和,则不满足条件,输出-1即可。

By:Wahacer

2018.04.16

22:43


HNOI考的人……心力交瘁。

颓颓颓。

发表评论

电子邮件地址不会被公开。 必填项已用*标注