• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ2516 – Minimum Cost

    ACM-POJ EXP 97阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    有N个供应商,M个店主,K种物品。每个供应商对每种物品的的供应量已知,每个店主对每种物品的需求量的已知,从不同的供应商运送不同的货物到不同的店主手上需要不同的花费,又已知从供应商Mj送第kind种货物的单位数量到店主Ni手上所需的单位花费。

    问:供应是否满足需求?如果满足,最小运费是多少?

    解题思路

    费用流问题

    (1)输入格式

    在说解题思路之前,首先说说输入格式,因为本题的输入格式和解题时所构造的图的方向不一致,必须要提及注意。以样例1为例:

    (2)题目分析和拆解

    A、首先处理“供应是否满足需求”的问题

    要总供应满足总需求,就必须有 每种物品的供应总量都分别满足其需求总量,只要有其中一种物品不满足,则说明供不应求,本组数据无解,应该输出-1。但是要注意这里判断无解后,只能做一个标记,但还要继续输入,不然一旦中断输入,后面的几组数据结果就全错了。

    而要知道“每种物品的供应总量都分别满足其需求总量”,对所有供应商第kind种物品的供应量求和ksupp[kind],对所有店主第kind种物品的需求量求和kneed[kind],然后比较ksupp[kind]与kneed[kind]就可以了。

    而最小费用流的计算是建立在“供等于求”或“供过于求”的基础上的


    B、最小费用问题

    要直接求出“把所有物品从所有供应商运送到所有店主的最小费用MinTotalCost”是不容易的。但是求出“把第kind种物品从所有供应商运送到所有店主的最小费用MinCost[kind]”却简单得多,这就转化为经典的多源多汇的费用流问题,而最后只需要把K种物品的最小费用求和 MinCost[kind],就能得到运送所有物品的最小费用MinTotalCost。

    其实题目的输入方式最后要输入K个矩阵已经暗示了我们要拆解处理。


    C、构图

    那么对于第kind种物品如何构图呢?

    解决多源多汇网络问题,必须先构造与其等价的单源单汇网络。构造超级源s和超级汇t,定义各点编号如下:

    超级源s编号为0,供应商编号从1到M,店主编号从M+1到M+N,超级汇t编号为M+N+1。

    令总结点数Nump=M+N+2,申请每条边的“花费”空间cost[Nump][ Nump]和“容量”空间cap[Nump][ Nump],并初始化为全0。

    超级源s向所有供应商M建边,费用为0,容量为供应商j的供应量。

    每个供应商都向每个店主建边,正向弧费用为输入数据的第kind个矩阵(注意方向不同),容量为供应商j的供应量;反向弧费用为正向弧费用的负数,容量为0。

    所有店主向超级汇t建边,费用为0,容量为店主i的需求量。

    注意

    1、其他没有提及的边,费用和容量均为0,容量为0表示饱和边或不连通。

    2、计算每种物品的最小费用都要重复上述工作重新构图,不过存储空间cost和cap不必释放,可重新赋值再次利用。


    D、求解

    对于第kind种物品的图,都用spfa算法求解最小费用路径增广链),再利用可分配最大流调MaxFlow整增广链上的容量,正向弧容量减去MaxFlow,反向弧容量减去MaxFlow,费用为单位花费乘以MaxFlow。

    具体的算法流程可参考我 POJ2195 的解题报告,基本一样。但注意的导致本题无可行解的原因只有“供不应求”,由输入数据知显然各边的容量均>=0,因此并不会出现负权环,spfa仍然用while循环直至无增广链为止足矣。


    转载请注明:EXP 技术分享博客 » POJ2516 – Minimum Cost

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址