题目大意

要建设一个村庄的网络

有两种操作可选

1、给中国移动交宽带费，直接连网，花费为 A。

2、向另外一座有网的建筑，安装共享网线，花费为 B×两者曼哈顿距离。

 

题解

显然的最小生成树的题

见一个虚拟源点，将每个点和那个虚拟源点连一个边权为A的边

其余每个点之间连边，边权即为曼哈顿距离*B

于是自信的以为曼哈顿距离就是两点之间的距离的我，怎么都过不了大样例，于是快乐gg，快乐崩溃...

 

#include
       
        #define ll long long#define db doubleusing namespace std;inline int read(){    int sum = 0,p = 1;    char ch = getchar();    while(ch < '0' || ch > '9')    {        if(ch == '-')            p = -1;        ch = getchar();    }    while(ch >= '0' && ch <= '9')    {        (sum *= 10) += ch - '0';        ch = getchar();    }    return sum * p;}const int N = 1e3 + 5;int n,A,B;struct node{    int x,y;} pot[N];int cnt,fa[N],tot;struct edge{    int frm,to;    ll wei;} e[N * N /2 + N];ll ans;void add(int a,int b,ll c){    e[++cnt].frm = a;    e[cnt].to = b;    e[cnt].wei = c;}bool cmp(edge a,edge b){    return a.wei < b.wei;}int findfa(int x){    if(fa[x] == x)        return x;    else        return fa[x] = findfa(fa[x]);}void kruskal(){    sort(e+1,e+cnt+1,cmp);    for(int i = 0;i <= n;i++)        fa[i] = i;    for(int i = 1;i <= cnt;i++)    {        int u = findfa(e[i].frm);        int v = findfa(e[i].to);        if(u == v)            continue;        fa[v] = u;        tot++;        ans += e[i].wei;        if(tot == n)            return;    }}int main(){    freopen("pupil.in","r",stdin);    freopen("pupil.out","w",stdout);    n = read(),A = read(),B = read();    for(int i = 1; i <= n; i++)    {        pot[i].x = read();        pot[i].y = read();    }    for(int i = 1; i <= n; i++)        for(int j = i + 1; j <= n; j++)        {            ll xx= abs(pot[i].x - pot[j].x);            ll yy= abs(pot[i].y - pot[j].y);;            add(i,j,(xx + yy) * B);        //    add(j,i,len * B);        }    for(int i = 1;i <= n;i++)    {        add(0,i,A);    //    add(i,0,A);    }    kruskal();    printf("%lld\n",ans);    return 0;}//不知道曼哈顿距离可还行