poj 3723 Conscription kruskal

缘起

日常水题 poj 3723 Conscription

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
需要征兵, 女兵N人，男兵M人. 每征募一个人需要花费$1w. 但是如果已经征募的人中有一些有亲密关系的人，那么
可以少花费一些钱. 给出若干对男女之间的1~9999之间的亲密值, 征募某个人的费用是10000-(已经征募的人中和
自己亲密度的最大值). 要求通过适当的征募顺序使得征募所有人花费的费用最小。

【输入】
多样例，第一行是样例数
每个样例第一行是N，M，R 然后R行每行是(x,y,d)——x和y之间的亲密度是d，假设
1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ xi < N
0 ≤ yi < M
0 < di < 10000

【输出】
每个样例输出最小花费

【样例输入】
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

【样例输出】
71071
54223

如果丝毫不考虑亲密度带来的减少花费的话，答案显然是 （N+M）*10000

但是因为有一些亲密关系——所以可以减免一些费用. 而输入的关系就构成未必连通的无向图（边的权是负值）. 我们可以将其分解为若干连通分支，然后对每个连通分支求MST——即求最小生成森林. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,m,r, cnt,f[20005]; // f是并查集数组

int getf(int i)
{
	return f[i]<0?i:f[i]=getf(f[i]);
}

bool merge(int i, int j)
{
	int fi =  getf(i), fj = getf(j);
	if (fi == fj)
	{
		return true;
	}
	if (f[fi]>f[fj])
	{
		f[fj]+=f[fi];
		f[fi] = fj;
	}
	else
	{
		f[fi]+=f[fj];
		f[fj] = fi;
	}
	return false;
}

struct Edge
{
	int a,b,c;
	bool operator <(Edge o)
	{
		return c<o.c;
	}
}e[50005];

int kruskal()
{
	int ans = 0;
	sort(e, e+cnt);
	for (int i = 0; i<cnt; i++) // 这cnt条边将以最小代价构成若干个连通分支
	{
		int a = e[i].a, b = e[i].b;
		if (merge(a,b))
		{
			continue;
		}
		ans+=e[i].c;
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		memset(f, -1, sizeof(f));
		cnt = 0;
		scanf("%d%d%d", &n, &m,&r);
		while(r--)
		{
			int a,b,c;
			scanf("%d%d%d", &a,&b,&c);
			e[cnt].a = a, e[cnt].b = n+b, e[cnt].c = -c; // 注意. 这里是-c（因为最后要减去亲密度）
			cnt++;
		}
		printf("%d\n", 10000*(n+m)+kruskal());
	}
	return 0;
}

ac情况

Status Accepted
Time 391ms
Memory 752kB
Length 1119
Lang C++
Submitted 2019-08-22 22:29:14
Shared
RemoteRunId 20789683