2017年9月16日提高组T2 A

Description

为了加快*现代化，建设学校，小明决定给学校里每台电脑都连上互联网，方便未来随时随地玩耍。
他的电脑室很大，有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

26
Hint

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

做法：相当于最小生成树，对于每一条权值大于a的边
直接替换为a，最后ans+a即可。
代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define min(x,y) (x) < (y) ? (x) : (y)
using namespace std;
struct arr
{
    long long x,y,w;
}f[1000001];
int a,n,b,x[10000],y[10000],g[10001];

long long abbs(long long x)
{
    if (x<0)    return 0-x;
    else return x;
}

long long cmp(arr q,arr p)
{
    return q.w<p.w;
}

long long find(long long z)
{
    if (g[z]==0)    return z;
    g[z]=find(g[z]);
    return g[z];
}

int main()
{
    //freopen("A.in","r",stdin);
    //freopen("A.out","w",stdout);
    scanf("%d%d%d",&n,&a,&b);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    long long e=0;
    for (int i=1;i<=n-1;i++)
        for (int j=i+1;j<=n;j++)
        {
            e++;
            f[e].x=i;
            f[e].y=j;
            f[e].w=b*(abbs(x[i]-x[j])+abbs(y[i]-y[j]));
        }
    sort(f+1,f+e+1,cmp);        
    long long ans=0;
    int p=0;
    for (int i=1;i<=e;i++)
    {
        if (find(f[i].x)!=find(f[i].y))
        {
            g[find(f[i].x)]=find(f[i].y);
            ans+=min(a,f[i].w);
        }
    }
    cout<<ans+a;
}