AcWing 3728. 城市通电(最小生成树)

时间:2021-07-22 23:37:30   收藏:0   阅读:32

参考讲解:https://www.acwing.com/video/3213/

题目

平面上遍布着 n 座城市,编号 1~n。
第 i 座城市的位置坐标为 (xi,yi)。
不同城市的位置有可能重合。
现在要通过建立发电站和搭建电线的方式给每座城市都通电。
一个城市如果建有发电站,或者通过电线直接或间接的与建有发电站的城市保持连通,则该城市通电。
在城市 i 建立发电站的花费为 ci 元。
在城市 i 与城市 j 之间搭建电线所需的花费为每单位长度 ki+kj 元。
电线只能沿上下左右四个方向延伸,电线之间可以相互交叉,电线都是双向的。
每根电线都是由某个城市沿最短路线搭建到另一个城市。
也就是说,如果在城市 i 与城市 j 之间搭建电线,则电线的长度为 |xi?xj|+|yi?yj|。
请问,如何合理设计通电方案,可以使得所有城市都成功通电,且花费最少?
输出最少花费和具体方案。
如果方案不唯一,则输出任意一种合理方案均可。

输入输出

输入:
第一行包含整数 n。
接下来 n 行,其中第 i 行包含两个整数 xi,yi,用来描述城市 i 的横纵坐标。
再一行包含 n 个整数 c1,c2,…,cn,用来描述每个城市建立发电站的花费。
最后一行包含 n 个整数 k1,k2,…,kn。
输出:
第一行输出所需要的最少花费。
第二行输出一个整数 v,表示需要建立发电站的数量。
第三行输出 v 个整数,表示建立发电站的城市编号,注意输出编号要在范围 [1,n] 内。且输出编号不应重复。输出编号顺序随意。
第四行输出一个整数 e,表示需要搭建的电线数量。
接下来 e 行,每行输出两个整数 a,b,表示要在城市 a 和 b 之间搭建电线。注意,任意两个城市之间最多只需要搭建一根电线,也就是说,对于每个 (a,b),不要有多余的 (a,b) 或 (b,a) 输出。a 和 b 不能相同,且要在范围 [1,n] 内。输出电线顺序随意。
如果答案不唯一,输出任意合理方案即可。

思路

将城市建立发电站看作是城市连了一条边到超级发电站,即超级源点,边的权值为城市建立发电站的费用ci。城市也可以连电线通往有电的城市,即一条边,边的权值为城市之间的曼哈顿距离。
当所有点与超级源点在一个连通块时,所有城市都有电。可以看成是最小生成树问题。
答案需要求最小生成树的权值。
该图是稠密图,用prim算法比Kruskal算法更好。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2010;
int n;
PII q[N];   //n个城市的坐标
int wc[N],wk[N];    //ci和ki
LL dist[N]; //存放点距离连通块最短的距离
int distp[N];    //存放当前距离连通块最短的点连到连通块的哪个点
vector<int> ans1;   //记录建发电站的城市
vector<PII> ans2;   //记录连电线的城市(一条边的两个顶点)
bool st[N]; //记录当前点在prim中是否被访问过了

LL get_dist(int a,int b){   //计算两个点之间的曼哈顿距离
    int dx = q[a].x - q[b].x;
    int dy = q[a].y - q[b].y;
    return (LL)(abs(dx) + abs(dy)) * (wk[a] + wk[b]);
}
LL prim(){
    LL res = 0;
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i ++ ){
        dist[i] = wc[i];    //初始化是都连发电站的值
    }
    dist[0] = 0;
    st[0] = true;
    for (int i = 0; i < n; i ++ ){  //将剩余n个点加入连通块中,操作n次
        int t = -1;
        for(int j = 1;j <= n;j++){  //选权值最小的点加入连通块
            if(!st[j] && (t == -1 || dist[t] > dist[j])) 
                t = j;
        }
        st[t] = true;
        res += dist[t]; //将t点加入到答案中 
        if(!distp[t]) ans1.push_back(t);    //直接连到发电站的答案
        else ans2.push_back({distp[t],t});    //连电线的答案
        //从t点开始更新其他点到连通块的最小距离
        for (int j = 1; j <= n; j ++ ){
            if(!st[j] && get_dist(j,t) < dist[j]){  //更新到连通块的最短距离
                dist[j] = get_dist(j,t);
                distp[j] = t;
            }
        }
    }
    return res;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> q[i].x >> q[i].y;
    for (int i = 1; i <= n; i ++ )
        cin >> wc[i];
    for (int i = 1; i <= n; i ++ )
        cin >> wk[i];
    LL res = prim();    //prim计算最小生成树的权值
    cout << res << endl;
    cout << ans1.size() << endl;    //输出发电站的数量
    for(int i = 0;i < ans1.size();i++)
        cout << ans1[i] << " ";
    cout << endl;
    cout << ans2.size() << endl;
    for (int i = 0; i < ans2.size(); i ++ )
        cout << ans2[i].x << " " << ans2[i].y << endl;
    return 0;
}

今天吃完晚饭出去逛了逛,分享今日美图:
技术分享图片

原文:https://www.cnblogs.com/Hfolsvh/p/15046435.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!