推 nypgand1:噢噢 跟hamiltonian的reduce很像耶 02/20 22:53
其實可以這樣
把每個點 v 拆成兩個點，並給一個流量為1的邊
eg. 有u,v兩個相鄰的點
v u
●-------●
，把它們拆成這樣
1
v_in v_out
●----------->●
1
●----------->●
u_in u_out
接著要把原本那個(u,v)邊加上去
圖不好畫，但就是把 u_out 連到 v_in， v_out 連到 u_in
對每個點都這樣做
然後把 starting vertices 的 in 端接到起點
把 edge vertices 的 out 端接到終點
就完成了
※ 引述《ybite (小犬)》之銘言：
: 還是趁著對題目有印象趕快發問...
: 這題不會，不過希望題目沒記錯
: 假若今天有一圖形如下
: ┌┬┬┬┬┬┬┬┬┬┐
: ├●┼┼┼┼┼┼┼┼┤
: ├┼┼┼┼┼●┼┼┼┤
: ├┼┼●┼┼┼┼┼┼┤
: ├┼┼┼┼┼┼┼┼┼┤
: ├┼┼┼┼┼┼●┼┼┤
: ├┼┼┼┼●┼┼┼┼┤
: ├●┼┼┼┼┼┼┼┼┤
: └┴┴┴┴┴┴┴┴┴┘
: 在這個圖中，要判斷每個●點都有一條和走到圖形外圍的路徑，
: 且圖形中不會出現兩條路徑共用同一邊（只要證出是否即可）
: 舉例來說：
: ┌┬┬┬┬┬┬┬┬┬┐
: ├●┼┼┼┼┼┼┼┼┤
: ├┼┼┼┼┼●┼┼┼┤
: ├┼┼●┼┼┼┼┼┼┤
: ├┼┼┼┼┼┼┼┼┼┤
: ├┼┼┼┼┼┼●┼┼┤
: ├┼┼┼┼●┼┼┼┼┤
: ├●┼┼┼┼┼┼┼┼┤
: └┴┴┴┴┴┴┴┴┴┘
: 真正的問題是：請把這個問題轉成一個Maxmium Flow問題...
: -------
: 本來以為很簡單，但是Maxmium flow不是單向的嗎？ @@
: 還是要做兩次？ @@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.156.187