算法刷题【一本通YbtOJ1488】新的开始
2022-04-12
先说句题外话，这个标题我很喜欢，种种原因吧做这道题的时候很emo（本来应该去写次小生成树的真的没有动力才来撕这道简单题）。做完一道水题，心情尚可了。
1488：新的开始
题目描述
发展采矿业当然首先得有矿井，小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井，但他似乎忘记考虑的矿井供电问题……
为了保证电力的供应，小 FF 想到了两种办法：
- 在这一口矿井上建立一个发电站，费用为 v（发电站的输出功率可以供给任意多个矿井）。
- 将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 p。
小 FF 希望身为「NewBe_One」计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。
输入格式
第一行一个整数 n，表示矿井总数。
第 2∼n+1 行，每行一个整数，第 i 个数 vi 表示在第 i 口矿井上建立发电站的费用。
接下来为一个 n×n 的矩阵 p，其中 pi,j 表示在第 i 口矿井和第 j 口矿井之间建立电网的费用（数据保证有pi,j=pj,i ，且 pi,i=0）。
输出格式
输出仅一个整数，表示让所有矿井获得充足电能的最小花费。
输入输出样例
In 1：
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0Out 1：
9样例解释
小 FF 可以选择在 4 号矿井建立发电站然后把所有矿井都不其建立电网，总花费是 3+2+2+2=9。
数据范围
对于 30% 的数据：1≤n≤50；
对于 100% 的数据：1≤n≤300,0≤vi,pi,j≤105 。
题解
看到这道题，第一眼的想法一定是去试在哪些地方放发电站吧，然而时间复杂度显然劝退。
正解：建立一个虚拟节点（编号可以分配 0 或者 n+1），每个点到这个点都有边连接，权值大小为当前点建发电站的费用。然后针对这总共 n+1 个点求最小生成树。
这样做的原理是每个点如果连接了真实的节点，则代表他连接了别的矿井的发电站；如果连接了这个虚拟节点，则代表新建了一座发电站。
总之无论如何最终都是保证了连通，你可以尝试在建完的最小生成树上删掉增加的虚拟节点和连接其的所有边，最小生成树拆解成了多个生成树，看起来是不是舒服、合理多了？
此时也很好证明正确性，因为（任何两个生成树之间连一条边的费用）都比（（在刚刚删掉的边上，除虚拟节点外的的另一个连接点）建一个发电站的费用）高。句子有点晦涩难懂，用括号辅助理解。
下面就来看代码吧：我的代码对比别人的稍有点长，但是可读性极强，稍耐心看一下别着急划走。
并查集用了类来实现因为这样子可以减少很多变量名冲突的问题，也不复杂。这么点小数据就不用路径压缩了不够烦的慌的。
#include <bits/stdc++.h>
using namespace std;
const int N = 301;
class BCJ {
private:
int f[N];
public:
void init() {
for (int i = 1; i <= N; i++) f[i] = i;
}
int find(int x) {
while (x != f[x]) {
x = f[x];
}
return x;
}
void merge(int x, int y) {
x = find(x);
y = find(y);
f[y] = x;
}
} bcj;
int n, v[N], p[N][N], es;
struct EDGE {
int from, to, w;
} edge[N * N * N];
bool cmp(EDGE x, EDGE y) { return x.w < y.w; }
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i];
edge[++es].from = i;
edge[es].to = 0;
edge[es].w = v[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> p[i][j];
edge[++es].from = i;
edge[es].to = j;
edge[es].w = p[i][j];
}
}
sort(edge + 1, edge + es + 1, cmp);
bcj.init();
int tot = 0;
for (int i = 1; i <= es; i++) {
int from = edge[i].from, to = edge[i].to, w = edge[i].w;
if (bcj.find(from) != bcj.find(to)) {
bcj.merge(from, to);
tot += w;
}
}
cout << tot << endl;
return 0;
}