这样阴沉的天气持续下去，我们不免担心起他的健康。
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 6Output示例
12思路： 这道题的思路是先去计算最小生成树，求得最小生成树中的最大链的魔法值 Max_Edge，然后用所有小于等于 Max_Edge的魔法链（满足条件魔法链的魔力值最大值尽可能的小）求得最大生成树（满足条件魔力值之和要尽可能的大）。
最小生成树有两种方法，Prim ( 未经优化）时间复杂度 n^2( n 为顶点数）， Kruskal 时间复杂为 mlog2(m)，m 为边的总数。
根据输入数据的规模，显而易见要用后者，也就是 Kruskal。
参考代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;typedef long long ll;
typedef struct edge {int s, e;ll v;
}Edge;bool cmp1(Edge A, Edge B) {return A.v < B.v;
}
bool cmp2(Edge A, Edge B) {return B.v < A.v;
}
const int N = 201000;
Edge a[N];
int f[N];
// f[i] != -1
// 则代表 i 与 f[i]之间有一条边int Find(int x) {if(f[x] == -1) return x;return f[x] = Find( f[x] );
}int n, m;
int kruskal_1() {// 返回最小生成树的最后一条边的下标 ans// Edge[ans].v 为最小生成树中的最大边memset(f, -1, sizeof(f)); // 初始化 f[]int sroot, eroot;int num = 0, ans = 1;for(int i=1; i<=m; i++) {sroot = Find(a[i].s);eroot = Find(a[i].e);if(sroot != eroot) {num ++;ans = i;f[sroot] = eroot;}if(num >= n-1) {break;}}if(num >= n-1) {return ans;}else {return -1;}
}ll Max_Edge;
ll kruskal_2() {// 在所有 小于等于 Max_Edge 的边中求得最大生成树memset(f, -1, sizeof(f));ll ans = 0, num = 0;int sroot, eroot;for(int i=1; i<=m; i++) {if(a[i].v > Max_Edge)continue;sroot = Find( a[i].s );eroot = Find( a[i].e );if(sroot != eroot) {num++;ans += a[i].v;f[sroot] = eroot;}if(num >= n-1)break;}if(num >= n-1)return ans;return -1;
}
int main(){cin >> n >> m;int s, e, v;for(int i=1; i<=m; i++) {scanf("%d %d %d", &s, &e, &v);a[i].s = s, a[i].e = e;a[i].v = v;}sort(a+1, a+m+1, cmp1); // 升序处理int index = kruskal_1();Max_Edge = a[index].v;//cout << Max_Edge << endl;sort(a+1, a+m+1, cmp2); // 降序处理cout << kruskal_2() ;return 0;
}