CF1245D Shichikuji and Power Grid 题解：超级源点的使用
Mr_Potato
·
·
题解
题意：
已知一个平面上有 n 个城市，需要个 n 个城市均通上电。
一个城市有电，必须在这个城市有发电站或者和一个有电的城市用电缆相连。
在一个城市建造发电站的代价是 c[i]，将 i 和 j 两个城市用电缆相连的代价是 k[i]+k[j] 乘上两者的曼哈顿距离。
求最小代价的方案。
思路
首先题目要求连通所有 n 个城市，很容易想到这是最小生成树。连通方式有：
我们设想一个有很多电的新城市，发现在城市中建发电站其实相当于连接到这个新城市。这就是本题的思路：超级源点。
我们将建发电站全部转化为连向序号为 0 的超级源点，每次建发电站就建立一条 0 连向该点的边，边权可以通过结构体构造函数直接计算。而其他边则每两条边连边即可，本题 n 的数据范围不超过 2000，则不会 \text{TLE}。那么我们接下来只需要跑一边 \text{Kruskal} 就可以 AC 本题了。
需要注意:
预处理时间复杂度 $\mathcal{O}(n^2)$，上限在于为每两座城市建边。
$\text{Kruskal}$ 时间复杂度 $\mathcal{O}(n^2 \log n^2)$。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,mst,cnt_to_zero,cnt_line;
int k[2010],c[2010];
struct Node {
int x,y;
Node() {}
Node(int a,int b) : x(a),y(b) {} // 构造函数
} node[2010];
int Manhatton(Node a,Node b) { // 曼哈顿距离
return abs(a.x - b.x) + abs(a.y - b.y);
}
struct Edge {
int u,v,w;
Edge() {}
Edge(int a,int b) : u(a),v(b) { // 构造函数
if (u == 0) { // 如果向超级源点连边
w = c[v]; // 边权即建发电站的代价
} else {
w = (k[u] + k[v]) * Manhatton(node[u],node[v]); // 按照题目条件计算
}
}
};
vector<Edge> edge;
vector<int> city_to_zero;
vector<Node> line;
class DSU { // 并查集
int fa[2010];
public :
void init(int size) {
for (int i=0; i<=size; ++i) {
fa[i] = i;
}
}
int find(int x) {
if (x != fa[x]) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void unite(int x,int y) {
fa[find(x)] = find(y);
}
} dsu;
int Kruskal() {
sort(edge.begin(),edge.end(),[](Edge a,Edge b) {
return a.w < b.w;
});
for (auto ver : edge) {
if (dsu.find(ver.u) != dsu.find(ver.v)) {
dsu.unite(ver.u,ver.v);
mst += ver.w;
if (ver.u == 0) {
++cnt_to_zero;
city_to_zero.push_back(ver.v == 0 ? ver.u : ver.v);
} else {
++cnt_line;
line.push_back({ver.u,ver.v});
}
}
}
return mst;
}
signed main() {
scanf("%lld",&n);
dsu.init(n);
for (int i=1; i<=n; ++i) {
scanf("%lld %lld",&node[i].x,&node[i].y);
}
for (int i=1; i<=n; ++i) {
scanf("%lld",&c[i]);
}
for (int i=1; i<=n; ++i) {
scanf("%lld",&k[i]);
}
for (int i=1; i<=n; ++i) {
edge.push_back({0,i}); // Kruskal里面无向边加一次就够了
for (int j=1; j<=n; ++j) {
edge.push_back({i,j});
}
}
printf("%lld\n",Kruskal());
printf("%lld\n",cnt_to_zero);
for (auto city : city_to_zero) {
printf("%lld ",city);
}
printf("\n%lld\n",cnt_line);
for (auto cityline : line) {
printf("%lld %lld\n",cityline.x,cityline.y);
}
return 0;
}
```