題目網址：3723 - Conscription
題目概述
Windy 要建立一支軍隊，他選了 N 個女孩與 M 個男孩。每招募一個「人」就要付出 10,000 人民幣。但在這些男孩女孩中，某些男孩與女孩存在著愛戀，並有個愛戀值 di。當招募的男孩與女孩有戀愛關係時，其中一個人的費用就可以降低為 10,000 - di。現在給出這些關係，求出 Windy 最少可以用多少錢招募這些男孩與女孩。要注意的是，每一個「人」都僅可以使用一條關係。
Technique Detail
- 女孩數量 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) 減去該權重和即為答案。
Time Complexity: O((N + M) × log R)
Source Code
| /* | |
| * ===================================================================================== | |
| * | |
| * Filename: 3723 - Conscription.cpp | |
| * | |
| * Description: http://poj.org/problem?id=3723 | |
| * | |
| * | |
| * Version: 1.0 | |
| * Created: 2012/02/16 14時59分31秒 | |
| * Revision: none | |
| * Compiler: gcc | |
| * | |
| * Author: KuoE0 (tommy790506@hotmail.com) | |
| * Organization: NCKU WMMKS Lab, Taiwan | |
| * | |
| * ===================================================================================== | |
| */ | |
| #include <iostream> | |
| #include <cstdlib> | |
| #include <cstdio> | |
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| #define MAXN 10010 | |
| vector< int > set, rank; | |
| int find_set( int x ) { | |
| if ( x != set[ x ] ) | |
| set[ x ] = find_set( set[ x ] ); | |
| return set[ x ]; | |
| } | |
| void union_set( int a, int b ) { | |
| if ( rank[ a ] > rank[ b ] ) | |
| set[ b ] = a; | |
| else { | |
| set[ a ] = b; | |
| if ( rank[ a ] == rank[ b ] ) | |
| ++rank[ b ]; | |
| } | |
| } | |
| int main() { | |
| int t, N, M, R; | |
| scanf( "%d", &t ); | |
| while ( t-- ) { | |
| vector< pair< int, pair< int, int > > > rel; | |
| scanf( "%d %d %d", &N, &M, &R ); | |
| set = rank = vector< int >( N + M, 0 ); | |
| for ( int i = 0; i < N + M; ++i ) | |
| set[ i ] = i; | |
| int x, y, d; | |
| for ( int i = 0; i < R; ++i ) { | |
| scanf( "%d %d %d", &x, &y, &d ); | |
| rel.push_back( pair< int, pair< int, int > >( d, pair< int, int >( x, N + y ) ) ); | |
| } | |
| long long int cnt = 0; | |
| sort( rel.begin(), rel.end(), greater< pair< int, pair< int, int > > >() ); | |
| for ( int i = 0; i < rel.size(); ++i ) { | |
| x = rel[ i ].second.first, y = rel[ i ].second.second; | |
| if ( find_set( x ) != find_set( y ) ) { | |
| cnt += rel[ i ].first; | |
| union_set( find_set( x ), find_set( y ) ); | |
| } | |
| } | |
| printf( "%lld\n", 10000 * ( long long )( N + M ) - cnt ); | |
| } | |
| return 0; | |
| } | |
Source code on gist.