洛谷题单指南-最小生成树-CF1245D Shichikuji and Power Grid

原题链接：https://www.luogu.com.cn/problem/CF1245D

题意解读：给n个城市供电，每个城市有坐标(x,y)，给城市i直接供电花费是c[i]，通过一个有电的城市i给没电的城市j供电花费是

(k[i]+k[j]) * (|x1-x2|+|y1-y2|)，求最少的花费，分别输出直接供电的城市数量、具体城市，以及间接供电的城市数量、具体城市对。

解题思路：

1、问题分析

此类题型前面已经出现过多次：

https://www.cnblogs.com/hackerchef/p/18830752

https://www.cnblogs.com/hackerchef/p/18838269

2、算法思路

对于这类既有点权，又有边权，求最小生成树的题，可以加入一个虚拟0点，跟所有点i建立连接，边长为c[i]

再预处理出所有1~n点之间相互供电的花费，作为边

运行kruskal算法求最小生成树，同时标记那些边被选择即可

100分代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2005, M = N * N;
struct Edge
{
    int u, v;
    LL w;
    bool ans1; //表示直接供电
    bool ans2; //表示间接供电
    bool operator < (const Edge &e) const
    {
        return w < e.w;
    }
} edges[M];
int cnt;
int x[N], y[N]; //坐标
int c[N]; //直接供电
int k[N]; //间接供电
int p[N]; //并查集
int n;
LL ans, cnt1, cnt2;

int dist(int i, int j)
{
    return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void kruskal()
{
    sort(edges + 1, edges + cnt + 1);
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= cnt; i++)
    {
        int a = find(edges[i].u);
        int b = find(edges[i].v);
        if(a != b)
        {
            p[a] = b;
            if(edges[i].u == 0) edges[i].ans1 = true, cnt1++; //u是0点则表示直接给v供电
            else edges[i].ans2 = true, cnt2++; //否则表示u给v间接供电
            ans += edges[i].w;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i <= n; i++) cin >> k[i];
    //虚拟0点
    for(int i = 1; i <= n; i++)
    {
        cnt++;
        edges[cnt].u = 0, edges[cnt].v = i, edges[cnt].w = c[i];
    }
    //预计算所有边
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            cnt++;
            edges[cnt].u = i, edges[cnt].v = j, edges[cnt].w = 1ll * (k[i] + k[j]) * dist(i, j);
        }
    }
    //求最小生成树
    kruskal();

    //输出结果
    cout << ans << endl;
    cout << cnt1 << endl;
    for(int i = 1; i <= cnt; i++)
    {
        if(edges[i].ans1) cout << edges[i].v << " ";
    }
    cout << endl;
    cout << cnt2 << endl;
    for(int i = 1; i <= cnt; i++)
    {
        if(edges[i].ans2) cout << edges[i].u << " " << edges[i].v << endl;
    }
    return 0;
}