题意：
有 n 个顶点，每个顶点有个花费 a[ i ]，连接顶点 u,v 需要花费 a[v]+a[u]的代价。
有 m 个特殊边，每条边有三个参数 u,v,w 代表的意思是连接 u,v 的花费可以不是 a[v]+a[u] 而是 w（当然选择小的那个啦）。
求联通所有的顶点需要的最少花费？
题解：
首先，需要建图，改如何建呢？
考虑到贪心的思路，首先不考虑 m 个特殊边，如何用最少的花费联通所有顶点呢？
答案是找到 a[ i ] 最少的顶点 i，其他 n-1 个顶点全部连向 i 。
将这 n-1 条边记录下来，在加上 m 条特殊边，然后，就是求最小生成树的模板题了，emmmmmm
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define ll __int64
#define pb(x) push_back(x)
const int maxn=2e5+; int n,m;
ll a[maxn];
struct Node
{
int u,v;
ll w;
Node(int a,int b,ll c):u(a),v(b),w(c){}
};
vector<Node >G;
void addEdge(int u,int v,ll w)
{
G.pb(Node(u,v,w));
} int fa[*maxn];
int Find(int x)
{
int r=x;
while(r != fa[r])
r=fa[r];
while(fa[x] != r)
{
int temp=fa[x];
fa[x]=r;
x=temp;
}
return r;
}
bool Union(int x,int y)
{
x=Find(x),y=Find(y);
if(x != y)
{
fa[x]=y;
return true;
}
return false;
}
bool cmp(Node _a,Node _b)
{
return _a.w < _b.w;
}
ll Solve()
{
sort(G.begin(),G.end(),cmp);
ll res=;
for(int i=;i < G.size();++i)
{
Node e=G[i];
if(Union(e.u,e.v))
res += e.w;
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
int minP=;
for(int i=;i <= n;++i)
{
fa[i]=i;
scanf("%I64d",a+i);
minP=(minP == || a[minP] > a[i] ? i:minP);
}
for(int i=;i <= n;++i)
addEdge(i,minP,a[i]+a[minP]);
for(int i=;i <= m;++i)
{
int u,v;
ll w;
scanf("%d%d%I64d",&u,&v,&w);
addEdge(u,v,w);
}
printf("%I64d",Solve());
return ;
}
Kruskal