[POJ] 3723 - Conscription

題目概述

Windy 要建立一支軍隊，他選了 N 個女孩與 M 個男孩。每招募一個「人」就要付出 10,000 人民幣。但在這些男孩女孩中，某些男孩與女孩存在著愛戀，並有個愛戀值 d_i。當招募的男孩與女孩有戀愛關係時，其中一個人的費用就可以降低為 10,000 - d_i。現在給出這些關係，求出 Windy 最少可以用多少錢招募這些男孩與女孩。要注意的是，每一個「人」都僅可以使用一條關係。

Technique Detail

女孩數量 N，1 ≤ N ≤ 10,000
男孩數量 M，1 ≤ M ≤ 10,000
關係數量 R，0 ≤ R ≤ 50,000
戀愛值 d_i，1 < d_i ≤ 10,000

輸入格式

測試資料開頭由一個整數 K 開始，表示接下來有 K 組測試資料。

每一組測試資料由三個整數開始 N M R，表示 Windy 要招募 N 個女孩與 M 個男孩，且這些男孩女孩中存在著 R 對關係。接著有 R 行，每行三個整數 x_i y_i d_i，表示女孩 x_i 與男孩 y_i 有存在著愛戀，且其愛戀值為 d_i。

輸出格式

對於每一筆測試資料，輸出一個整數，表示最少 Windy 最少付出多少費用可以招募到他所需要的士兵。

解題思路

原本往二分匹配的方向去想了，但看了看資料量，男孩與女孩的數量都達到 10,000 且關係也達到 50,000。如此大的資料量，使用 KM 都不見得能在實現內完成，更何況使用 max flow 的演算法。於是放棄了匹配的想法，也因為這樣仔細重新看題目，發現是每個「人」都可以使用一條關係。因此不代表使用了某條關係後，該關係聯繫的兩人都無法在與其他關係匹配了。反而可以選擇該關係給其中一個人，而另一個人若有其他關係可使用時，則可多選擇一條關係。

所以這樣連接後，其實就是一棵樹，而這棵樹的權重和就是可以節省的費用。因此需要讓該樹的權重和越大越好，所以其實就是找出最大生成樹。而男孩與女孩就都看成圖上的點即可，僅需要將他們的編號重新編制，以免有重複的號碼。在套用如 Kruskal 或是 Prim 等最小生成樹的演算法即可找出最大權重和。最後 10,000 * (N + M) 減去該權重和即為答案。

Time Complexity: O((N + M) × log R)

Source Code

Source code on gist.