作者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