CF 1245D题解

· · 题解

前置知识：

曼哈顿距离：

即对于坐标为 (x_1,y_1) 的 a 点和坐标为 (x_2,y_2) 的 b 点，它们的曼哈顿距离为 \vert x_1-x_2 \vert + \vert y_1-y_2 \vert。

思路：

有点权有边权还要求最小方案，容易想到建虚点然后跑最小生成树。

首先以 0 为虚点向 n 个城市建边，边权为每个城市建造发电站的代价 c_i。

然后就是每个城市之间建边，边权为 k_i+k_j 乘上两者的曼哈顿距离。

然后就跑最小生成树，虽然本题是稠密图，用 Prim 会更优，但 Kruskal 更好写，并且本题的数据范围用 Kruskal 来做是能过的。

注意，别忘了开 long long。

双倍经验：CF 938D

（思路与本题大同小异，无非就是对边权的处理不同）。

// Problem: CF1245D Shichikuji and Power Grid
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1245D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By:Komorebi_03
#include<bits/stdc++.h>
using namespace std;
#define int long long
//不要忘记开 long long
const int N = 1e6+5;
int n,sum,ans,tot,e_cnt,st_cnt,u[N],v[N],x[N],y[N],c[N],k[N],st[N],fa[N];
struct edge{
    int u;
    int v;
    int w;
}e[5*N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

void add(int u,int v,int w)
{
    e[++e_cnt].u=u;
    e[e_cnt].v=v;
    e[e_cnt].w=w;
}

int Find(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=Find(fa[x]);
}

bool cmp(edge a,edge b)
{
    return a.w<b.w;
}

void Kru()
{
    sort(e+1,e+1+e_cnt,cmp);
    for (int i=1;i<=e_cnt;i++)
    {
        int U=e[i].u;
        int V=e[i].v;
        int W=e[i].w;
        int r1=Find(U);
        int r2=Find(V);
        if(r1!=r2)
        {
            fa[r1]=r2;
            sum++;
            ans+=W;
            //判断是否需要建立发电站
            if(!e[i].u)
                st[++st_cnt]=e[i].v;
            else
            {
                u[++tot]=e[i].u;
                v[tot]=e[i].v;
            }
        }
        if(sum==n)
            break;
    }
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
        fa[i]=i;
    //别忘记初始化
    for (int i=1;i<=n;i++)
    {
        x[i]=read();//点的横坐标
        y[i]=read();//点的纵坐标
    }
    for (int i=1;i<=n;i++)
    {
        c[i]=read();
        add(0,i,c[i]);
        //以 0 为虚点建图，边权为每个点建发电站的代价
    }
    for (int i=1;i<=n;i++)
        k[i]=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            int C=(k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j]));
            //跑最小生成树前先把边权进行处理，即 (k[i] + k[j]) * 两者的曼哈顿距离
            add(i,j,C);
        }
    }
    Kru();
    cout<<ans<<"\n"<<st_cnt<<"\n";
    for (int i=1;i<=st_cnt;i++)
        cout<<st[i]<<" ";
    putchar('\n');
    cout<<tot<<"\n";
    for (int i=1;i<=tot;i++)
        cout<<u[i]<<" "<<v[i]<<"\n";
    return 0;
    //Amireux_35
}