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