假設我的人口分散在有水源的固定區域中。每個水源都有一個訪問范圍，并且可以與其他水源重疊。我必須將每個水源分配給每個人，以免每個水源超載太多人（假設每個水源最多 n 人）。每個人只能有一個來源。我如何最大限度地擴大覆寫范圍，包括某些可能由于超載而無法訪問的可能性？
您擁有每個人的潛在水源。
uj5u.com熱心網友回復：
這個答案使用圖論。這里有一個介紹
這是一個最大流量問題：
p_i為每個人制作一個頂點w_j為每個水源制作一個頂點- 制作源頂點
S和匯頂點T - 從水源到每個人做一個邊緣
p_i，容量1（每個人只能有一個水源） - 對于每個人，如果此人在水源范圍內，則
p_i對每個水源做一個邊緣w_j - 對于每個水源
w_j，為水槽做一個邊緣，其容量等于該水源可以容納的最大人數。
然后求解最大流量。由于水源只有 n 的“輸出”容量，因此只能有“n”人連接到該水源。
如果將人們分組到社區中，您可以通過將他們分組來更快地進行，但是您必須以S社區人口的能力從社區中脫穎而出。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/522510.html
標籤：算法
上一篇：在不使用陣列的情況下反轉JavaScript中的字串
下一篇：使用c語言的陣列中沒有重復的數字