题目: 基准时间限制：1 秒 空间限制：131072 KB
51nod魔法学校近日开展了主题为“天气晴朗”的魔法交流活动。
N名魔法师按阵法站好，之后选取N - 1条魔法链将所有魔法师的魔力连接起来，形成一个魔法阵。
魔法链是做法成功与否的关键。每一条魔法链都有一个魔力值V，魔法最终的效果取决于阵中所有魔法链的魔力值的和。
由于逆天改命的魔法过于暴力，所以我们要求阵中的魔法链的魔力值最大值尽可能的小，与此同时，魔力值之和要尽可能的大。
现在给定魔法师人数N，魔法链数目M。求此魔法阵的最大效果。
Input
两个正整数N，M。(1 <= N <= 10^5, N <= M <= 2 * 10^5) 接下来M行，每一行有三个整数A, B, V。(1 <= A, B <= N, INT_MIN <= V <= INT_MAX) 保证输入数据合法。
Output
输出一个正整数R，表示符合条件的魔法阵的魔力值之和。
Input示例
4 6
1 2 3
1 3 1
1 4 7
2 3 4
2 4 5
3 4 6
Output示例
12 关于思路: 这道题可以先用最小生成树求出最大权值边，然后再用权值小于等于最大权值的边做一次最大生成树的做法求解 代码如下:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
typedef long long LL;
using namespace std;
const int maxn=;
struct node{
LL u,v,w;
node(){}
node(LL a,LL b,LL c):u(a),v(b),w(c){}
};
LL f[maxn];
LL n,m;
vector<node>edge;
int Find(LL x)
{
if (f[x] != x)
f[x] = Find(f[x]);
return f[x];
} void Union(LL a, LL b)
{
int a1 = Find(a);
int b1 = Find(b);
if (a1 != b1)
f[a1] = b1;
}
bool cmp1(node a,node b)
{
return a.w>b.w;
}
bool cmp2(node a,node b)
{
return a.w<b.w;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=n;i++)
f[i]=i;
for(int i=;i<m;i++){
LL a,b,c;
cin>>a>>b>>c;
edge.push_back(node(a,b,c));
}
sort(edge.begin(),edge.end(),cmp2);
LL k=,max_num=-;
for(int i=;i<m;i++)
{
if(Find(edge[i].u)!=Find(edge[i].v))
{
Union(edge[i].u,edge[i].v);
max_num = max(max_num,edge[i].w);
k++;
}
if(k==(n-))
break;
}
sort(edge.begin(),edge.end(),cmp1);
for(int i=;i<=m;i++)
f[i]=i;
LL ans=;
k=;
for(int i=;i<m;i++)
{
if(edge[i].w>max_num)continue;
if(Find(edge[i].u)!=Find(edge[i].v))
{
Union(edge[i].u,edge[i].v);
ans += edge[i].w;
k++;
}
if(k==(n-))
break;
}
cout<<ans<<endl;
return ;
}