※ 引述《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