Problem Solving and Programming- hw6

31 Oct 2017

Online-Judge

Programming / Graph Theory / Kattis / KTH

題目連結

pA - GopherII

今天有 $n$ 隻老鼠和 $m$ 個洞，當老鷹來的時候，老鼠們要躲到洞裡才不會被吃掉，但有以下限制。

一個洞只能容納一隻老鼠
老鼠只能跑到一定範圍以內的洞，太遠跑不到

想問說最後有幾隻老鼠會被吃掉。\
這題頗水，根據題目給定的座標及限制，建一個二分圖去對老鼠和洞們做匹配，算幾隻老鼠沒被配到。

$|E| = nm$ , $|V| = n+m$ ，用最大流求二分匹配的話，複雜度 $O(VE(V+E))$ \
(不過題目沒給輸入範圍，應該就是怎樣都會過…lol)

pB - XYZZY

今天有 $n$ 個房間，每個房間蘊含著可正可負的能量(?)，一個冒險者想從房間 $0$ 走到房間 $n-1$ 。他一開始有能量 $100$ 點，每經過一個房間便會獲得該房間的能量，而當他走到最終房間或是能量用完時，遊戲結束，想問說他有沒有可能走到最終房間。這題目包含了一些假設讓我們比較好解。

在房間之間移動不耗費能量
同一個房間可以走好幾次(可以一直拿能量)
只在乎到不到的了，不在乎步數最少
最後一個房間蘊含能量 $0$ (所以你到它時，能量一定要 $\mathbf{> 0}$ ，等號不成立)

我們先把題目轉成有向圖，每個節點 $v$ 代表一個房間，其出邊上的 weight 為該房間蘊含的能量。今天我們想去 maxmize 到每一點還保有的能量，然後看 energy[n-1] 是否大於 $0$ ？

是一個求單源最短路的變形，而因為有負邊，所以只能用 Bellman-Ford 來做。而有些名詞要做些修正。

NEG_CYCLE $\rightarrow$ POS_CYCLE (可以在正能量迴圈中繞，能量源源不絕)
UNREACHABLE $\rightarrow$ energy $= 0$

Relax 也要改一下， $\forall e=(u,v)$

if(energy[u] != 0 && energy[u] + e.w > energy[v])
  relax energy[v] = energy[u] + e.w

先用 bfs 從終點拓展，看哪些房間到的了它，在 Bellman-Ford 跑第二個迴圈偵測正環時， $\forall e=(u,v)$

if exist POS_CYCLE at u:
  if 終點 is reached by u:
    return True

如果上述判式在迴圈都沒成立，則 check energy[n-1] 是否 $> 0$

pC - Risk

給定一張圖，裡頭的點有些是你的，有些是敵人的，而在每個點上有一些士兵。\
給定圖中這些點與點相鄰與否的關係，及起始圖上每個點你的士兵有多少，在每個士兵至多移動一次的情況下(留在原地或移動到鄰近且屬於你的點)，想 maximize 與敵軍相鄰最弱點的士兵數，且每個點至少要留守一個士兵。\
Note:同一點的士兵們，不用一起移動，可分別決定要到哪個鄰近點或留守(有點廢話，但一開始卡了一下)

這題我是用最大流的想法來解，假設最弱點士兵數為 $k$ ，建一張屬於你的點的二分圖，如果相鄰的話，該邊的 capacity 就是原先在該點的士兵數(當然自己也要連到自己，因為可以留在原地)。最後將這些點連到 sink ，而當中邊的權重，如果該點不與敵軍相鄰，capacity 為 1，如果與敵軍相鄰則是 $k$ ，然後檢查是否滿流(滿流代表走一次的情況下，所有與敵軍相鄰點的士兵數均 $\geq k$ )，然後用二分搜去找出最大的 $k$ 。複雜度為 $\mathcal{O}(\log ( \text{army})n n^2(n + n^2)) = \mathcal{O}(\log ( \text{army}) n^5)$

這題也很棒！如果推廣可以移動 $m$ 步的話，就在加 $m$ 個 layer，如果有相鄰的話，第二層之後，最後一層連到 sink 之前，就設權重為 $\sum_{army}$

pD - Full Tank

開車旅行，當中有 $n$ 個城市，城市間有道路相連，每個城市有加油站，且單位油價各不相同，給定起點及終點，想找一條花費油錢最小的行程。

感覺就是個求單源最短路徑的問題，但 criteria 略有不同 (但油錢多少跟距離也正相關)，因為邊權非負，不妨嘗試用 Dijkstra 的想法解解看。但我們現在需要多考慮現存油量 $f$ 這個變數。

$$ cost[i][f]: \quad \text{min. cost when arriving } \, i\text{-th city with fuel} \, f $$

struct State{
  int idx,fuel,cost;
  State(int idx,int fuel,int cost):idx(idx),fuel(fuel),cost(cost){}
  bool operator<(const State& rhs) const {return cost > rhs.cost;}
};

而 state 的轉移(或說Relax)有兩個選擇：

在原地加 $1$ 單位的油
花費 $d_e$ 單位的油，移動到別的城市

跟 Dijkstra 一樣 maintain 一個 priority queue，每次 pop out 出一個 state 做 Relax ，直到第一次 pop out 出的城市為終點，或queue 變為 empty (卻還沒成功，代表起點終點不連通) 而 Relax 的 condition 就是上述兩個狀態轉移的方式。

加一單位的油

if(cost[i][f+1] > cost[i][f] + prices[i]) 
  relax(cost[i][f+1])

移動到鄰近城市 $\forall j \in N(i)$

if(cost[j][f-e.weight] > cost[i][f])
  relax(cost[j][f-w.weight])

關於複雜度，state 總數為 $nC$ ( $C$ 為油箱的 capacity)，如果用 binary heap 的話，

Extract-Min: $\mathcal{O}(\log (nC))$ ，需要至多 $nC$ 次
INS(state不會重複，cost 會嚴格遞增，不是用 Decrease): $\mathcal{O}(\log (nC))$ ，需要至多 $2mC$ 次

Graphs II

pA - GopherII

pB - XYZZY

pC - Risk

pD - Full Tank