【Prim算法】城市通电

题目

3728. 城市通电 - AcWing题库

---

平面上遍布着 $n$ 座城市，编号 $1 \sim n$ 。

第 $i$ 座城市的位置坐标为 $(x_i,y_i)$ 。

不同城市的位置有可能重合。

现在要通过建立发电站和搭建电线的方式给每座城市都通电。

一个城市如果建有发电站，或者通过电线直接或间接的与建有发电站的城市保持连通，则该城市通电。

在城市 $i$ 建立发电站的花费为 $c_i$ 元。

在城市 $i$ 与城市 $j$ 之间搭建电线所需的花费为每单位长度 $k_i+k_j$ 元。

电线只能沿上下左右四个方向延伸，电线之间可以相互交叉，电线都是双向的。

每根电线都是由某个城市沿最短路线搭建到另一个城市。

也就是说，如果在城市 $i$ 与城市 $j$ 之间搭建电线，则电线的长度为 $|x_i-x_j|+|y_i-y_j|$ 。

请问，如何合理设计通电方案，可以使得所有城市都成功通电，且花费最少？

输出最少花费和具体方案。

如果方案不唯一，则输出任意一种合理方案均可。

输入格式

第一行包含整数 $n$ 。

接下来 $n$ 行，其中第 $i$ 行包含两个整数 $x_i,y_i$ ，用来描述城市 $i$ 的横纵坐标。

再一行包含 $n$ 个整数 $c_1,c_2,…,c_n$ ，用来描述每个城市建立发电站的花费。

最后一行包含 $n$ 个整数 $k_1,k_2,…,k_n$ 。

输出格式

第一行输出所需要的最少花费。

第二行输出一个整数 $v$ ，表示需要建立发电站的数量。

第三行输出 $v$ 个整数，表示建立发电站的城市编号，注意输出编号要在范围 $[1,n]$ 内。且输出编号不应重复。输出编号顺序随意。

第四行输出一个整数 $e$ ，表示需要搭建的电线数量。

接下来 $e$ 行，每行输出两个整数 $a,b$ ，表示要在城市 $a$ 和 $b$ 之间搭建电线。注意，任意两个城市之间最多只需要搭建一根电线，也就是说，对于每个 $(a,b)$ ，不要有多余的 $(a,b)$ 或 $(b,a)$ 输出。 $a$ 和 $b$ 不能相同，且要在范围 $[1,n]$ 内。输出电线顺序随意。

如果答案不唯一，输出任意合理方案即可。

数据范围

对于前三个测试点， $1 \le n \le 3$ 。
对于全部测试点， $1 \le n \le 2000$ ， $1 \le x_i,y_i \le 10^6$ ， $1 \le c_i,k_i \le 10^9$ 。

输入样例1：

3
2 3
1 1
3 2
3 2 3
3 2 3

输出样例1：

8
3
1 2 3 
0

输入样例2：

3
2 1
1 2
3 3
23 2 23
3 2 3

输出样例2：

27
1
2 
2
1 2
2 3

解题

方法一：朴素Prim算法

思路

本题需要让所有城市都通上电，很容易想到求最小生成树，但是在本题中让城市能通上电的手段不只有拉电线，还可以自己建电站，这样以来就会导致形成多个连通块而求不了 MST 。

解决方案是：创造一个虚拟源点 $0$ ，把所有 自己开发电站的城市 都看作是向顶点 $0$ 连了一条边，而这条边的边权为 $c_i$ （即建立发电站的花费），这这样一来就可以对构造出来的这个完全图求一个最小生成树的最小总权重即为需要的最少花费。

在本题中任意两个城市之间都可以拉电线，任意一个城市都可以建电站，所以必然是一个稠密图，用朴素Prim算法求解即可。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final long INF = 0x3f3f3f3f3f3f3f3fL;
    static int n;
    static int[][] poses; // 所有城市的坐标
    static int[] ks; // 搭建电线所需的花费
    static long[][] g; // 邻接矩阵存图
    static List<Integer> gens = new ArrayList<>(); // 答案: 需要建立发电站的城市
    static List<int[]> lines = new ArrayList<>(); // 答案: 需要搭建的电线
    
    // 计算在x与y之间搭建电线所需要的费用
    static long getDist(int x, int y) {
        return (ks[x] + ks[y]) * 1L
            * (Math.abs(poses[x][0] - poses[y][0]) + Math.abs(poses[x][1] - poses[y][1])); 
    }
    
    // 朴素Prim算法
    static long prim() {
        long[] dists = new long[n + 1];
        int[] from = new int[n + 1]; // 存当前个点是被哪个点所更新的
        Arrays.fill(dists, INF);
        Arrays.fill(from, -1);
        boolean[] vis = new boolean[n + 1];
        long res = 0L;
        // 加上虚拟源点总共n+1个点 所以根据Prim算法的原理循环n+1次
        for (int i = 0; i <= n; ++i) {
            int mn = -1;
            for (int j = 0; j <= n; ++j) {
                if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
            }
            if (i > 0) {
                if (dists[mn] == INF) return INF; // 本题为完全图 必存在MST 所以这句可以去掉
                res += dists[mn]; // 更新生成树最小权值
                // 存答案
                if (from[mn] == 0) gens.add(mn);
                else lines.add(new int[]{from[mn], mn});
            }
            vis[mn] = true;
            prev = mn;
            for (int j = 0; j <= n; ++j) {
                if (g[mn][j] < dists[j]) {
                    dists[j] = g[mn][j];
                    // 记录j是由mn更新过来的
                    from[j] = mn;
                }
            }
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        poses = new int[n + 1][2];
        g = new long[n + 1][n + 1];
        ks = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            poses[i][0] = (int) in.nval;
            in.nextToken();
            poses[i][1] = (int) in.nval;
        }
        // 搭建发电站的费用 直接在图里跟虚拟源点连
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            g[0][i] = g[i][0] = (int) in.nval;
        }
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            ks[i] = (int) in.nval;
        }
        // 建图
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (i == j) continue;
                g[i][j] = g[j][i] = getDist(i, j);
            }
        }
        long ans = prim();
        StringBuilder sb = new StringBuilder();
        sb.append(ans).append('\n').append(gens.size()).append('\n');
        for (int u : gens) sb.append(u).append(' ');
        sb.append('\n').append(lines.size()).append('\n');
        for (int[] edge : lines) sb.append(edge[0]).append(' ').append(edge[1]).append('\n');
        System.out.print(sb);
    }
}