【-85】P1550 [USACO08OCT]打井[最小生成树]

题目描述

Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.
Digging a well in pasture i costs W_i (1 <= W_i <= 100,000).
Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).
Determine the minimum amount Farmer John will have to pay to water all of his pastures.
POINTS: 400

农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若
干井,并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。
请求出农民John 需要为连通整个牧场的每一块田地所需要的钱数。

输入输出格式

输入格式:

第1 行为一个整数n。
第2 到n+1 行每行一个整数,从上到下分别为W_1 到W_n。
第n+2 到2n+1 行为一个矩阵,表示需要的经费(P_ij)。

输出格式:

只有一行,为一个整数,表示所需要的钱数。

输入输出样例

输入样例#1:

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

输出样例#1:

9

说明

John等着用水,你只有1s时间!!!

题解

最小生成树.
先新建一个点,然后所有的点连一条边过去,边权为挖一口井的费用
然后跑最小生成树就可以了//注意:本题是稠密图,所以prim会比克鲁斯卡尔快

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
#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
int u,v,w;
int id;
}a[200000];
int p[200000];
int d,m;
int b;
int fa[200000];
int X;
int ans;
bool cmp(node aa,node bb)
{
return aa.w<bb.w;
}
inline void add(int x,int y,int z)
{
d++;
a[d].u=x;a[d].v=y;a[d].w=z;a[d].id=p[x];p[x]=d;
}
int gf(int x)
{
if (fa[x]==x) return x;
fa[x]=gf(fa[x]);
return fa[x];
}
int sum;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
fa[i]=i;
scanf("%d",&b);
add(i,n+1,b);//与n+1连边,边权:费用
add(n+1,i,b);
}
fa[n+1]=n+1;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
scanf("%d",&X);
if (i!=j) add(i,j,X);//加边
}
m=d;
sort(a+1,a+m+1,cmp);
for (int i=1;i<=m;i++)
{
int x1=gf(a[i].u);int x2=gf(a[i].v);
if (x1!=x2)
{
sum++;
ans+=a[i].w;
fa[x1]=fa[x2];
}
if (sum==n) break;
}
printf("%d",ans);
return 0;
}