| layout | title | date | tags | |||
|---|---|---|---|---|---|---|
post |
[POJ] 3723 - Conscription |
2012-02-16 |
|
題目網址：3723 - Conscription
Windy 要建立一支軍隊，他選了 N 個女孩與 M 個男孩。每招募一個「人」就要付出 10,000 人民幣。但在這些男孩女孩中，某些男孩與女孩存在著愛戀，並有個愛戀值 di。當招募的男孩與女孩有戀愛關係時，其中一個人的費用就可以降低為 10,000 - di。現在給出這些關係，求出 Windy 最少可以用多少錢招募這些男孩與女孩。要注意的是，每一個「人」都僅可以使用一條關係。
- 女孩數量 N，1 ≤ N ≤ 10,000
- 男孩數量 M，1 ≤ M ≤ 10,000
- 關係數量 R，0 ≤ R ≤ 50,000
- 戀愛值 di，1 < di ≤ 10,000
測試資料開頭由一個整數 K 開始，表示接下來有 K 組測試資料。
每一組測試資料由三個整數開始 N M R，表示 Windy 要招募 N 個女孩與 M 個男孩，且這些男孩女孩中存在著 R 對關係。接著有 R 行，每行三個整數 xi yi di，表示女孩 xi 與男孩 yi 有存在著愛戀，且其愛戀值為 di。
對於每一筆測試資料，輸出一個整數，表示最少 Windy 最少付出多少費用可以招募到他所需要的士兵。
原本往二分匹配的方向去想了，但看了看資料量，男孩與女孩的數量都達到 10,000 且關係也達到 50,000。如此大的資料量，使用 KM 都不見得能在實現內完成，更何況使用 max flow 的演算法。於是放棄了匹配的想法，也因為這樣仔細重新看題目，發現是每個「人」都可以使用一條關係。因此不代表使用了某條關係後，該關係聯繫的兩人都無法在與其他關係匹配了。反而可以選擇該關係給其中一個人，而另一個人若有其他關係可使用時，則可多選擇一條關係。
所以這樣連接後，其實就是一棵樹，而這棵樹的權重和就是可以節省的費用。因此需要讓該樹的權重和越大越好，所以其實就是找出最大生成樹。而男孩與女孩就都看成圖上的點即可，僅需要將他們的編號重新編制，以免有重複的號碼。在套用如 Kruskal 或是 Prim 等最小生成樹的演算法即可找出最大權重和。最後 10,000 * (N + M) 減去該權重和即為答案。
<script src="https://gist.github.com/KuoE0/1843223.js"></script>Time Complexity: O((N + M) × log R)
Source code on gist.