推 yalight:我發覺我搞錯題目了 ... 我在想想 XD 140.115.205.19 06/25 01:50
※ 引述《yalight (ㄚ光)》之銘言：
: ※ 引述《march20 ()》之銘言：
: : Btw, 這個 reduction 看來不對喔.
: : vvv 你是說 destination 嗎?
: 不是 我是說全部的 edge
: : ^^^^^^ 今天討論的是雙 source 版本
: 我指的是題目的 S 那個 vertex,
: 反正要想成 max-flow 的 source 的話也很簡單
: capacity=2 capacity=∞
: source -----------> S=Graph=T -------------> sink
: cost=0 cost=0
: source 和 sink 是 max-flow 的
: 黃色是原題目的 graph
: 希望看的懂 orz
: : 目前你的 reduction 看來不完整,
: : 來問一個問題就可以知道你的 reduction 是怎麼一回事了.
: : 呃, 找到 max-flow 之後, 試問原題對應的解為何?
: min-cost
ok, 考慮以下graph,
100
s1---------->t1 <---
/ \1 \ \
S/ x------- \T /
\ \ / /
\ \ / /
s2---------->t2 /
\ 100 /
\ /
y-----------
怕這圖不清楚, 再用文字說明一次:
s1,s2,t1,t2,x,y 型成為原題給的 graph, 其中 edge 為
s1->t1 (weight = 100)
s2->t2 (weight = 100)
s1->x (weight = 1)
s2->y (weight = 1)
x ->t2 (weight = 1)
y ->t1 (weight = 1)
沒錯, 這樣找確實可以找到邊不重複的解,
但是會變成 s1->t2, s2->t1 而原題要找的是 s1->t1, s2->t2
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.136.245.92