Facebook編程挑戰 - ByteLand

Question

ByteLand Byteland由編號爲1..N的N個城市組成。有M條公路連接一些城市對。有兩個軍隊師，A和B，保護王國。每個城市要麼由陸軍師A，要麼由陸軍師B保護。

你是敵國的統治者，並且制定了摧毀拜特蘭的計劃。你的計劃是摧毀Byteland的所有道路，破壞所有的溝通。如果你攻擊任何一條路，來自兩條連接城市的軍隊都是爲了防守。你意識到如果軍隊A和B都有士兵防禦任何道路，你的攻擊就會失敗。

所以你決定在實施這個計劃之前，你會攻擊一些城市並擊敗位於城市的軍隊，使你的計劃成爲可能。然而，這是相當大的難度。你估計擊敗位於城市的軍隊將佔用大量的資源。你的目標現在是決定攻擊哪個城市，使你的成本是最小的，沒有路應該從兩軍A和B.

被保護----請告訴我，如果這種做法是正確的----

我們需要根據摧毀城市所需的資源對城市進行排序。對於每個城市，我們需要詢問以下問題：

1）刪除了以前的城市是不是會導致可以破壞Byteland的州？

2）它連接任何道路嗎？

3）它是否連接任何由不同的城市武裝的道路？

如果所有這些條件都滿足，我們將繼續朝着摧毀城市和記錄迄今爲止所遭遇的總成本，並確定這個城市的破壞將導致Byteland的整體破壞。

由於城市按照成本增加的順序排列，我們可以在任何地方找到所需的刪除組。

Answer 1

你只需要關心以不同的軍隊連接兩個城市的道路 - A和B或B和A之間的鏈接之間的聯繫，讓我們刪除從A到A或B的所有鏈接B.

你想找到一組點，使得每個鏈接上至少有一個點，這是一個最小權重頂點覆蓋。在任意圖上，這將是NP完全的。但是，您的圖只有類型A的節點鏈接到類型B的節點，或者相反 - 它是具有這兩種類型的節點作爲雙方的雙向圖。所以，你可以通過使用一種算法尋找最小重量頂點找到一個最小重量頂點覆蓋上二部圖覆蓋。尋找這個，我發現例如http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/assignments/sol5.pdf

Answer 2

mcdowella，

但頂點具有成本，對他們的最低點覆蓋不會產生正確的頂點刪除。設想2個頂點（軍隊）指向第三個（B）。前兩個頂點每個花費1，其中第三個花費5個。最小頂點覆蓋將返回第三個頂點覆蓋 - 但移除第三個頂點花費比以成本1 + 1移除兩個節點更多。

我們可能需要一些此處最小頂點覆蓋的修改版本。