描述

http://poj.org/problem?id=3155

一個公司內部共n個員工，員工之間可能曾經因為小事有了過節，總是鬧矛盾。若員工u和員工v有矛盾，用邊(u, v)表示，共m個矛盾。最近，公司內部越來越不團結，要裁員。想得到一個被裁人員的清單，使得被裁人員間的不團結率最高。不團結率定義為被裁人員間的矛盾總數與被裁人員數的比值（不團結率= 被裁人員之間的矛盾總數/ 被裁人員數）。

---

題解：

如果把一個矛盾定義為一條邊，一位員工定義為一個點，那么這里的不團結率就對應著一個圖的密度：圖的一個子圖中邊數與點數的比值。不團結率最大就對應著密度最大。本題就要求求出圖的最大密度子圖。

·簡單分析：求最大密度子圖的方法就是用最大閉合子圖。將每個點和每個邊都看成一個結點來處理?？芍?#xff1a;如果選擇一個邊(u，v)，那么必須選擇兩個點u、v，這就符合了最大閉合子圖的約束條件。然后二分答案g，只要邊數 / 點數 ≥ g，就證明還有更大的密度可以取到。

·思路：關鍵是判斷下面的條件如何判斷成立：

邊數點數≥g要對這個不等式進行變形： =>1?邊數?g?點數≥0
這樣就很清晰了，將每個邊設為一個點權為1的結點，每個點設為一個點權為-g的結點。求最大閉合子圖，如果權值大于g，就說明還有更大密度的存在。

建模：建立附加源s和附加匯t，將每條邊作為一個結點ei，和他相鄰的點分別是結點ui、vi。從s向每個ei連一條容量為1的邊。從每個ui、vi向t連一條容量為g的邊。從每個ei向相鄰ui、vi連一條容量為INF的邊。

實現：統計邊數Total，二分答案g，每次都要重新建圖求解最大流Maxflow。如果在某一g處剛好有此時的

Total?Maxflow<0那么g-1就是答案。

還有優化的方法，不過看不懂……

總結

以上是生活随笔為你收集整理的[POJ 3155] Hard Life的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。