SSL 2731_村通网_最小生成树

发布于 2017-09-16  916 次阅读

题目描述

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

 

思路

将全部点相连，边权为两点的两者曼哈顿距离*B

在用一个点i'和全部点相连全职为A

跑最小生成树即可

 

#include 
#include 
using namespace std;
#define maxn 10000005
struct edge
{
    int x, y, w;    
}e[maxn];
struct arr
{
    int x, y;
}a[1005];
int f[1006];
int abs(int x)
{
    if (x < 0) return -x;
    return x;
}
int cmp(edge a, edge b)
{
    return a.w < b.w;
}
int find(int x)
{
    if (f[x] == x) return x;
    f[x] = find(f[x]);
    return f[x];
}
int insert(int x, int y)
{
    if (find(x) != find(y))
    {
        f[find(x)] = find(y);
        return 1;
    }
    return 0;
}
int main()
{
    int n, A, B;
    scanf("%d%d%d", &n, &A, &B);
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
        scanf("%d %d", &a[i].x, &a[i].y);
    }
    int l = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            e[++l] = (edge){i, j, B * (abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y))};
    for (int i = 1; i <= n; i++)
        e[++l] = (edge){0, i, A};
    sort(e + 1, e + l + 1, cmp);
    int ans = 0;
    for (int i = 1; i <= l; i++)
    {
        if (find(e[i].x) != find(e[i].y))
        {
            ans += e[i].w;
            insert(e[i].x, e[i].y); 
        }
    }
    printf("%d\n", ans);
}

 

 

]]>