作業(yè)示例單題tunnels解題報(bào)告

1、WorldFinalsProblem解題報(bào)【題目簡(jiǎn)述一個(gè)無(wú)向圖，spy 1 0 spy的逃跑路線并且任何時(shí)候都可以選擇摧毀任何一條道路，使得 spy 無(wú)法逃跑到 數(shù)據(jù)范圍 ： n 50，m【算法分析spy spy無(wú)法從 1 號(hào)點(diǎn)逃跑到 0 號(hào)點(diǎn)，問(wèn)最少需要摧毀幾條道路這是一個(gè)非常經(jīng)典的問(wèn)題，解決方法是求源點(diǎn)(S) 為 1，匯點(diǎn)(T ) 為 0 的無(wú)向圖的最大流最小割來(lái)求出至S T spy 的逃 f (i)表示spy i 出發(fā)，使用最優(yōu)策略逃跑最少需要摧毀幾條道路初始的時(shí)候f (i) ，定義一條路徑 y 當(dāng)這條路徑上至少有一個(gè)點(diǎn)的f 值y可以用以下方法去迭代更新 f (i)：如果存在兩個(gè)數(shù) x，

2、y0，滿足摧毀掉 條道路后，所有從點(diǎn)i到點(diǎn)0的所有路徑全部y，那么就用x+y來(lái)更f(i)f (i)是不斷減小的，這樣的迭代一定可以結(jié)束，并且無(wú)論迭代的順序f(i)f(i)值一首先f(wàn)(i)一定是一個(gè)合法解：f(i)=x+y，那么先摧毀掉x條道路，使得i0的路徑全部yspyf值 y的結(jié)點(diǎn)上，而還有y次摧毀機(jī)會(huì)，不妨設(shè)這個(gè)點(diǎn)為j ，f (j) x0 y0 y ，那么可個(gè)過(guò)程，那么 spy 一定無(wú)法成功逃跑所以迭代后的 f (i)一定是滿足條件G 刪掉了一條邊后的圖，現(xiàn)在對(duì)兩個(gè)圖分別迭代 f(i)值，那么 f(i f(if(i f(i1f(i)=pip-1spy一定可以成i0的p的路徑，如果不存在，可

3、以用 x 0, y p 1f (i)f (i) x y p 1 f(i) = p 矛盾 spy 使用最優(yōu)策略，就一定會(huì)沿著一條p 的路徑逃跑，你可以選擇摧毀這spy jp-2 次摧毀的fjfj1f1，而你1spy f值1的點(diǎn)，而你沒(méi)有任何摧毀機(jī)會(huì)了，這樣spyf (i)一x+yf (i)，這個(gè)過(guò)程顯然不好實(shí)現(xiàn)，因?yàn)榇輾男┑缆?，這樣的可能性達(dá) 從點(diǎn) i 出發(fā)到點(diǎn) 0 最少需要摧毀幾條道路，根據(jù)本文最開(kāi)始提到的那個(gè)問(wèn)題，可以知道計(jì)算 x 只需要求一遍從點(diǎn) i 0 的最大流最小割即可注意到，如果當(dāng)前圖中 f 值最小的點(diǎn)為 i，那么可以用 f(i)+x 去更新i k End ForEnd至此問(wèn)題完美解決，時(shí)間復(fù)雜度為O(n2 *max flow(nm)，如果使Dinic，最大流的時(shí)間復(fù)雜度是 O(n2m)，因