JZOJ 5353. 【NOIP2017提高A组模拟9.9】村通网DescriptionInputOutputSample InputSample OutputData ConstraintSolutionCode

101 阅读 0 评论 67 点赞

我是靠谱客的博主优雅野狼，这篇文章主要介绍JZOJ 5353. 【NOIP2017提高A组模拟9.9】村通网DescriptionInputOutputSample InputSample OutputData ConstraintSolutionCode，现在分享给大家，希望可以做个参考。

Description

为了加快社会主义现代化，建设新农村，农夫约(Farmer Jo)决定给农庄里每座建筑都连上互联网，方便未来随时随地网购农药。
他的农庄很大，有N 座建筑，但地理位置偏僻，网络信号很差。
一座建筑有网，当且仅当满足以下至少一个条件：
1、给中国移动交宽带费，直接连网，花费为A。
2、向另外一座有网的建筑，安装共享网线，花费为B×两者曼哈顿距离。
现在，农夫约已经统计出了所有建筑的坐标。他想知道最少要多少费用才能达到目的。

Input

第一行：三个正整数，代表N、A、B。
接下来N 行：每行两个整数Xi、Yi，第i 行代表第i 座建筑的坐标。

Output

第一行：一个整数，代表答案。

Sample Input

5 10 2
0 0
0 1
1 0
1 1
100 100

Sample Output

Data Constraint

30%的数据：N <= 3，A <= 50，B <= 5
60%的数据：N <= 100，A <= 1000，B <= 20
100%的数据：N <= 10^3，A <= 10^4，B <= 50，|Xi|,|Yi| < 2^15

Solution

这题是一道简单的最小生成树裸题。
一个点 i 向另一个点 j 连一条权值为 dist(i,j)∗B 的边，其中 dist(i,j) 表示两点的曼哈顿距离。
如何处理“直接联网”的情况呢？于是再加入一个虚点 0 。
点 0 向每一个点各连一条权值为 A 的边，做最小生成树时将 0 也做进去即可。
显然，这 n+1 个点（包括 0 <script type="math/tex" id="MathJax-Element-777">0</script> ）构成的最小生成树即为答案。

Code

复制代码

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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1001;
struct data
{
LL x,y,z;
}a[N],b[2*N*N];
int tot;
LL ans;
int f[N];
inline LL read()
{
LL X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline LL dist(int i,int j)
{
return abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
}
inline bool cmp(data x,data y)
{
return x.z<y.z;
}
inline int get(int x)
{
if(f[x]==x) return x;
return f[x]=get(f[x]);
}
int main()
{
int n=read();
long long A=read(),B=read();
for(int i=1;i<=n;i++)
{
a[i].x=read(),a[i].y=read(),f[i]=i;
for(int j=1;j<i;j++)
{
b[++tot].x=j;
b[tot].y=i;
b[tot].z=dist(i,j)*B;
}
}
for(int i=1;i<=n;i++)
{
b[++tot].x=0;
b[tot].y=i;
b[tot].z=A;
}
sort(b+1,b+1+tot,cmp);
for(int i=1,k=0;i<=tot;i++)
{
int f1=get(b[i].x),f2=get(b[i].y);
if(f1!=f2)
{
f[f1]=f2;
ans+=b[i].z;
if(++k==n) break;
}
}
printf("%lld",ans);
return 0;
}