最小生成树之中中救援队 （安慰奶牛）

题目

思路

（听说是原题？？叫安慰奶牛）
最小生成树板子？？？？直接把来回跑两遍话花费赋值为一条边权上

add(x,y,z*2+w[x]+w[y]);

然后跑Kruskal？？

记得把价值最小的节点作为跟节点再加上，输出就行了

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10,maxm=200000+10;
int w[maxn],fa[maxn],n,m,tot,Min=0x7f7f7f7f;
struct edge{int dis,from,to;}e[maxm];
void add(int x,int y,int z){e[++tot].from=x;e[tot].to=y;e[tot].dis=z;}
bool com(edge a,edge b){return a.dis<b.dis;}
int find_root(int x){
    if(fa[x]==x) return x;
    fa[x]=find_root(fa[x]);
    return fa[x];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
		Min=min(Min,w[i]);
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z*2+w[x]+w[y]);
	}
	sort(e+1,e+tot+1,com);
	int ans=Min,cnt=0;
	for(int i=1;i<=tot;i++){
		int a=e[i].from,b=e[i].to;
		if(find_root(a)==find_root(b)){
			continue;
		}
		else{
			cnt++;
			fa[find_root(a)]=find_root(b);
			ans=ans+e[i].dis;
		}
	}
	printf("%d
",ans);
}