【题解】一本通最小生成树·新的开始

原题

发展采矿业当然首先得有矿井， 小FF花了上次探险获得的千分之一的财富请人在岛上挖了$n$口矿井， 但他似乎忘记考虑的矿井供电问题…… 为了保证电力的供应， 小FF想到了两种办法：

1. 在这一口矿井上建立一个发电站，费用为$v$（发电站的输出功率可以供给任意多个矿井）。
2. 将这口矿井与另外的已经有电力供应的矿井之间建立电网， 费用为$p$。小FF希望身为”NewBe_One" 计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。

输入

第一行一个整数$n$， 表示矿井总数。

第$2$～$n+1$行，每行一个整数， 第$i$个数$v[i]$表示在第$i$口矿井上建立发电站的费用。

接下来为一个$n*n$的矩阵$P$， 其中$p[ i , j ]$表示在第i口矿井和第j口矿井之间建立电网的费用（数据保证有$p[ i, j ] = p[ j, i ]$, 且 $p[ i, i ]=0$）。

输出

仅一个整数， 表示让所有矿井获得充足电能的最小花费。

样例输入

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

样例输出

9

提示

无

题目大意

最小生成树。唯一的难点是如何表示发电站，后来想到可以把一个点有发电站看成这个点和0点的连线。然后跑一遍$kruskall$就A了。

算法

最小生成树 $kruskall$算法

代码

#include<bits/stdc++.h>
using namespace std;
int a[1010];//并查集函数
int n,sum=0;
int find(int x){
	//并查集查询操作
	if(a[x]==x) return x;
	return a[x]=find(a[x]);//路径压缩
}
struct node{
	int a,b,w;
};
bool cmp(node a,node b){
	return a.w<b.w;//自定义排序，也可以重载运算符
}
vector<node>e;//边
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i]=i;//并查集初始化
		int p;
		cin>>p;
		e.push_back({0,i,p});//把发电站看成和0点的连线
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int t;
			cin>>t;
			if(i>=j) continue;
			e.push_back({i,j,t});//普通的边
		}
	}
	sort(e.begin(),e.end(),cmp);//排序
	for(auto it:e){
		//kruskall算法
		int fa=find(it.a),fb=find(it.b);
		if(fa!=fb){
			a[fa]=fb;
			sum+=it.w;//累加权值
		}
	}
	cout<<sum;//输出
}

感谢观看$qwq$！