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

    ACM-POJ EXP 141阅读 0评论

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


    解题思路

    多源多汇最大流问题

    提示:BFS找增广链 + 压入重标法

    题目给出很多都是废话,特别是符号s(u),d(u),Con还有那条公式都别管,混淆视听

    难点在于构图

    电站p(u)均为源点,用户c(u)均为汇点,中转站当普通点处理

    第一个误区是例图, 结点 和 边 都有x/y(流量和容量),这个很容易使人产生矛盾(因为学习最大流问题是,只有 边 才有流量和容量。

    但是不难发现,题目所给的例图中有多个源点,多个汇点,多个普通点,只有源点和汇点才标有 x/y,普通点没有标x/y,而且所给出的所有边都有x/y。 这无疑在促使我们对图做一个变形: 建议一个超级源s,一个超级汇t,使s指向所有源点,并把源点的 容量y 分别作为这些边的 容量,使所有汇点指向t,并把汇点的容量y分别作为这些边的 容量,然后本来是源点和汇点的点,全部变为普通点。这样就把“多源多汇最大流”变形为“单源单汇最大流”问题

    第二个误区就是流量值。 学习最大流问题时,会发现边上的流量值是给定初始值的,但是这题的输入只有容量,没有流量,很多人马上感觉到无从入手。其实边上的流量初始值为多少都没有所谓,解最大流需要用到的只有容量。但是一般为了方便起见, 会把所有边的流量初始化为0。这样做有一个最大的好处,就是可以回避 反向弧 的存在,这个下面详细叙述。


    本题中要注意的是:

    1、 如果输入中,某一点上有环,就无视掉。环是否存在不影响最终结果。

    2、 一般两点之间都是单边,一旦存在双边也没有问题,因为由定义知两个方向的容量一定相等(其实不相等也无妨,因为其中有一条为 反向弧,前面已经提到 反向弧 是可以直接回避、无视的,因此反向弧上的容量为多少就不重要了),而且在寻找增广路的标号过程中,搜索的是未标号的点,就是说(u,v)这条弧即使是双向的,但一旦从u到达v后,就不能回头了,因为两者都被标记了,即另外一条弧就不起任何作用了。

    下面详细说说为什么能够回避反向弧

    首先需要明确,任意一个点j上记录的信息有:
       1、 寻找增广路时,除超级源s外,增广路上任一点j都有一个唯一的前驱i(i被记录在j)
       2、 min{从i到j的容流差,l(vi)}
       3、 构图时,除超级汇t外,图上任一点j都会直接指向一些点(这些点作为后继点,同在记录在j)

    从这个特点可以知道,从超级源开始寻找增广路时,万一遇到双向边,正向弧,反向弧自动被回避。万一遇到单向边,如果是非饱和正向弧,就会继续走下去;如果是反向弧,这条弧必然是 零弧(每条边初始化流量均为0),定义知如果增广路有反向弧,它必须要是 非零弧,而且由于反向弧每次都不会经过,所以在改进增广路时反向弧上的流量也不会被改变,永远为0,也就与最终结果无关了

    最后当无法寻找增广路时,最大流就是与超级源s直接关联的边上的 流量之和

    转载请注明:EXP 技术分享博客 » POJ1459 – Power Network

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

    表情

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

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