需要簡單的圖解解決問題的建議

Question

我的一個同事向我提出一個網上法官網站的練習，這個網站基本上是解決小城鎮疏散計劃問題的圖表。

我不需要答案（我也不需要它）我只需要一個建議，哪個是最好的方法來解決它，因爲我有點新來這些類型的問題。

這個問題包括城鎮建築與工人和隕石坑以防核襲擊。我必須建立一個算法，將每個建築物的工作人員分配到一個或多個放射性庇護所，但某些庇護所不會變得過於擁擠，而其他庇護所仍然幾乎空無一人（否則，我只會讓工人去最近的一個） 。

的問題是這樣的：http://acm.timus.ru/problem.aspx?space=1&num=1237

萬一

其下線繼承人谷歌的緩存版本的它：http://webcache.googleusercontent.com/search?q=cache:t2EPCzezs7AJ:acm.timus.ru/problem.aspx%3Fspace%3D1%26num%3D1237+vladimir+kotov+evacuation+problem&cd=1&hl=pt-PT&ct=clnk&gl=pt

我做了什麼至今每個建築物離您最近的住房和移動的號碼這些建築的工人數量與住房的能力相當。然後移動到下一座建築物。但有時候工作人員的數量大於住房容量，在這種情況下，在我遍歷每個建築物之後，不正確的迭代，然後再次使用相同的算法，直到每個建築物都有0名工人，問題在於這並不是最好的方法解決這個問題。

歡迎任何提示，請不要覺得我要求的答案，我只是想解決它的正確方向的意見。

在此先感謝。

Answer 1

這看起來正好像Transhipment Problem它可以（顯然）使用線性規劃求解。 （我明顯地說，因爲這看起來是整數線性編程的一個實例）。

從網站：

標準的方案，其中一個 運輸出現問題是跨 網絡連接 給定的城市公路發送產品單位 。每個城市 被認爲是「來源」，在 中，單位將從 發運出去，或作爲「接收器」，在那裏需要單位 。每個源具有 給定的電源中，每個散熱器具有一個給定的需求 ，並且每個連接 一個源 - 匯對高速公路具有每 裝運單元的給定 運輸成本。這可以通過網絡的形式在 中可視化，如下圖 圖TP-1所示。

鑑於這樣的網絡，的 感興趣的問題是要確定最小化 出貨的總成本的最佳 運輸方案，受試者 供應和需求約束。

希望有所幫助。

Answer 2

這看起來像一個標準的Min-cost max flow問題。具有〜200個頂點的二分圖應該很容易及時運行。要創建頂點約束（每個節點只能處理k個人），您只需創建第二個圖G_1，在其中爲每個v_i添加一個附加頂點u_i - 並且將流v_i添加到u_i中，無論您的約束條件如何在這種情況下，k + 1，成本爲0.所以基本上，如果原始圖G中存在邊（a，b），那麼在G_1中，將會有一個邊（u_a，v_b）這些邊緣。實際上，您正在創建第二層頂點，將每個頂點的流量限制爲k。