P1550-[USACO08OCT]Watering Hole G
题目:
题目描述:
Farmer John 的农场缺水了。
他决定将水引入到他的 $n$（$1 \leq n \leq 300$）个牧场。他准备通过挖若干井，并在各块田中修筑水道来连通各块田地以供水。在第 $i$ 号田中挖一口井需要花费 $W_i$（$1 \leq W_i \leq 10^5$）元。连接 $i$ 号田与 $j$ 号田需要 $P_{i,j}$（$1 \leq P_{i,j} \leq 10^5$，且 $P_{j,i}=P_{i,j}$）元。
请求出 FJ 需要为使所有农场都与有水的农场相连或拥有水井所需要的最少钱数。
输入格式:
第一行为一个整数 $n$。
接下来 $n$ 每行一个整数 $W_i$。
接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 个数表示连接 $i$ 号田和 $j$ 号田需要的费用 $P_{i,j}$。
输出格式:
输出最小开销。
样例:
样例输入1:
1
2
3
4
5
6
7
8
9
| 4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
|
样例输出1:
思路:
实现:
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
| #include "ybwhead/ios.h"
int n;
struct bi
{
int a, b, c;
} e[100001];
int f[10001];
int find(int x)
{
if (f[x] == x)
return x;
return f[x] = find(f[x]);
}
int cmp(bi a, bi b)
{
return a.c < b.c;
}
int main()
{
yin >> n;
for (int i = 1; i <= n; i++)
{
int t;
yin >> t;
e[i].a = 0;
e[i].b = i;
e[i].c = t;
}
int sum = n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
int c;
yin >> c;
if (c)
{
e[++sum].a = i;
e[sum].b = j;
e[sum].c = c;
}
}
}
sort(e + 1, e + sum + 1, cmp);
int ans = 0;
for (int i = 1; i <= n; i++)
f[i] = i;
for (int i = 1; i <= sum; i++)
{
int sa = find(e[i].a), sb = find(e[i].b);
if (sa != sb)
{
f[sa] = sb;
ans += e[i].c;
}
}
yout << ans << endl;
return 0;
}
|