GOOD NIGHT
诸位，这是最小生成树的模板（掌声）
以下是题目链接：FOR——MIKU
代码如下
/*
并查集可以解决最小生成树的问题 因为并查集可以完成高效的合并 但是，以下代码依赖于一个重要前提 ，就是每两棵树之间只有一根线，不然，以下代码绝对不行 证明： 在Ａ,B之间有三条边，边值为1,2,3；
按照以下思路，排序后是3,2,1；
当我们处理3时，我们把A，B合进了一个集中；
然而，当我们处理到2,1时，我们会检查到A,B已经在了同一个集合！！！！！！！
所以说我们的代码不会删除2,1这两条边！！！！！！！
这样就从根本上否决了最小生成树，因为两点之间有2条及以上边 */
#include<iostream>
#include <algorithm>
#include<cstdio>
#include<algorithm>
#include<algorithm>
#include<algorithm>
#include<ctime>
using namespace std;
int n,k,fa[]; int sum; struct bian{
int start;
int last;
int diss;
}biann[]; /*
这个并查集就是依赖于只有一条边，从大到小按权值删 */
bool cmp(bian x,bian y)
{
return x.diss<y.diss;
} int find(int x)
{
if(fa[x]!=x)
return find(fa[x]);
return x;
} int main()
{
cin>>n>>k;
for(int i=;i<=n;++i)//并查集部分
fa[i]=i;
for(int i=;i<=k;++i)
{
cin>>biann[i].start>>biann[i].last>>biann[i].diss;
sum+=biann[i].diss;//得到权值和，因为用并查集做题是删边
}//存图部分
sort(biann+,biann++k,cmp);
for(int i=;i<=k;++i)//并查集部分
{//以下部分仅依赖于前提
int r1=find(biann[i].start);
int r2=find(biann[i].last);
if(r1 != r2)
{//这部分有点贪心了，因为只要搜到，在一块，就一定是最短了，因为只有一条边
fa[r1]=r2;
sum-=biann[i].diss;//并查集是删边
}
}
cout<<sum; return ; }