POJ 3723 Conscription(kruskal算法求最大權森林問題)

Conscription

Time Limit: 1000MS

 

Memory Limit: 65536K

Total Submissions: 9673

 

Accepted: 3437

Description

Windy has a country, and he wants to build an army to protect his country. He has picked up N girls and M boys and wants to collect them to be his soldiers. To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these relationships to reduce his cost. If girl x and boy y have a relationship d and one of them has been collected, Windy can collect the other one with 10000-d RMB. Now given all the relationships between girls and boys, your assignment is to find the least amount of money Windy has to pay. Notice that only one relationship can be used when collecting one soldier.

Input

The first line of input is the number of test case.
The first line of each test case contains three integers, N, M and R.
Then R lines followed, each contains three integers x_i, y_i and d_i.
There is a blank line before each test case.

1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ x_i < N
0 ≤ y_i < M
0 < d_i < 10000

Output

For each test case output the answer in a single line.

Sample Input

2

5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781

5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133

Sample Output

71071
54223

 

題意：需要招募女兵N人，男兵M人。每招募一個人需要花費10000元。但是如果已與招募的人中有一些關系親密的異性，那麼可以少花一些錢。 給出R條男女間1~9999的關系值，招募某人的費用為10000-（已經被招募的人中與其關系值的最大值）。要求通過適當的順序招募所有人，使得所需要的費用最少。

 

題解：x，y分別表示女兵和男兵。題目中男女有對應關系，但男兵，女兵都是從編號零開始。並不在一棵樹裡。我們可以把y=y+N，這樣就要男生加到女生的書中成為了一棵樹。我們需要找到這棵樹的最大邊權值（原費用(N+M)*10000-最大邊權值才等於最少花費），可以把所有的邊權值變為自身的負值。這樣最大權森林問題就變成了最少生成樹問題。

 

轉變為最少生成樹後，就變成了一道裸題。prim算法處理是在矩陣存儲中容易出錯，也會容易爆內存。鄰接表+prim更好。 我這裡用的kruskal，很方便。

 

代碼如下：

 

 

#include
#include
#include
using namespace std;
#define maxn 10010
int tree[maxn*2];
struct node
{
	int x,y,d;
}a[50010]; //注意數組啊，以R的范圍開 

int cmp(node a,node b)
{
	return a.d