作者JonathanWang (尹儿)
看板ACMCLUB
标题Re: [问题] pku 1637
时间Tue Aug 9 10:24:52 2005
※ 引述《yalight (ㄚ光)》之铭言：
: http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1637
: 请问这题要怎麽做呢？
: 想不出来怎麽用 max flow 解？@@"
: <(_ _)>
那重贴一遍好了 :P
首先, 一定要是连通的. 然後..
先考虑单向的边, 它总是从某 x 走到某 y, 而且一定要走,
所以对每一条这样的边, 把它的 x 点的值 (原本是 0) 减 1
而 y 点的值加 1.
然後我们面对的是一个只剩双向边, 并且每个点上都有一些值的图.
现在的目标就是要把每一个边走掉, 并且要取用适当的方向, 使得各点的值能平衡.
那就来造一个 flow 的图.
造一个源点和一个汇点. 从源点连边到每一个正值的点上, 而且容量就是那个值;
从每一个负值的点连边到汇点, 而且容量就是那个值 (把负号拿掉).
而在图上的边, 就让它们的容量是 1 (两个方向都是 1), 然後作 max-flow.
如果源点流出去的, 没有把流出去的容量用完, 那就不存在解;
如果有用完, 那继续...
把图上被流过的边拿掉 (或许还会剩下一些边).
检查是不是每一个点的 degree 都是偶数, done.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.42