51nod 1640 天气晴朗的魔法【二分+最大生成树】

1640 天气晴朗的魔法 题目来源： 原创 基准时间限制：1 秒 空间限制：131072 KB 分值: 20  难度：3级算法题 这样阴沉的天气持续下去，我们不免担心起他的健康。 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

思路：

1、首先考虑，让生成树的值最大，那么肯定是要求最大生成树，问题在于，如何确定最大边权。

2、让最大边权值的边权值尽可能的小，那么很明显，我们就是在求一个具有边权上限的最大生成树，那么如何让这个边权值尽可能的小呢？

①我们考虑枚举一个值，然后判断小于等于这个值的边能否构成一个生成树，我们从最小值开始向上枚举，枚举到第一个值，使得其能够构成一个生成树为止，那么这个值，就是我们要求的。接下来我们以这个值为上界，求一个最大生成树的总权值即可。

②但是这么直接枚举显然时间复杂度很高，考虑到这样一点：我们枚举的值越大，能够构成生成树的可能性就越大，那么显然其具有单调性，那么我们考虑二分优化即可。

3、注意数据范围比较大，需要用LL.

那么整体思路就是：

①二分这个上界值，使得这个值是一个界限，如果低于这个值，我们就不能构成生成树。

②然后根据二分出来的这个上界值，求一颗最大生成树即可。

但是好像我的做法有点麻烦了，Ａｃ之后看到各位巨巨的思路，都是先求一遍最小生成树，将此时的最大边记录下来，那么这个最大边显然就是上界值，那么我们接下来以上界值再做一遍最大生成树即可。

Ａｃ代码（二分思路的）：

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define ll __int64 struct node { int x,y; ll w; }a[500060]; int cmp(node a,node b) { return a.w>b.w; } ll ans; int n,m; int f[500060]; int find(int a) { int r=a; while(r!=f[r]) { r=f[r]; } int i=a; int j; while(i!=r) { j=f[i]; f[i]=r; i=j; } return r; } void merge(int x,int y) { int xx=find(x); int yy=find(y); if(xx!=yy) { f[xx]=yy; } } int Slove(ll mid) { int k=0; for(int i=1;i<=n;i++)f[i]=i; for(int i=0;i<m;i++) { if(a[i].w<=mid) { if(find(a[i].x)!=find(a[i].y)) { k++; merge(a[i].x,a[i].y); } } } if(k==n-1) { return 1; } else return 0; } int main() { while(~scanf("%d%d",&n,&m)) { ll maxn=0; for(int i=0;i<m;i++) { scanf("%d%d%I64d",&a[i].x,&a[i].y,&a[i].w); maxn=max(maxn,a[i].w); } sort(a,a+m,cmp); ll l=0; ll r=maxn; ll ans=0; while(r-l>=0) { ll mid=(l+r)/2; if(Slove(mid)==1) { ans=mid; r=mid-1; } else { l=mid+1; } } for(int i=1;i<=n;i++)f[i]=i; ll output=0; for(int i=0;i<m;i++) { if(a[i].w<=ans) { if(find(a[i].x)!=find(a[i].y)) { merge(a[i].x,a[i].y); output+=a[i].w; } } } printf("%I64d\n",output); } }

效率榜第一的巨巨的Ａｃ代码（感谢巨巨分享的代码）（先求最小生成树再求最大生成树的做法）：

#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; typedef struct Road { int x, y; int len; bool operator < (const Road &b) const { if(len<b.len) return 1; return 0; } }Road; Road s[200005]; int ufs[100005]; int Find(int x) { if(ufs[x]==0) return x; return ufs[x] = Find(ufs[x]); } int main(void) { int n, m, i, t1, t2, temp, sum; long long ans; scanf("%d%d", &n, &m); for(i=1;i<=m;i++) scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].len); sort(s+1, s+m+1); sum = 0; for(i=1;i<=m;i++) { t1 = Find(s[i].x); t2 = Find(s[i].y); if(t1!=t2) { ufs[t1] = t2; sum++; } if(sum==n-1) break; } ans = 0, temp = i; memset(ufs, 0, sizeof(ufs)); while(temp<m && s[temp].len==s[temp+1].len) temp++; for(i=temp;i>=1;i--) { t1 = Find(s[i].x); t2 = Find(s[i].y); if(t1!=t2) { ufs[t1] = t2; ans += s[i].len; } } printf("%lld\n", ans); return 0; }