51nod 1640 天气晴朗的魔法 【二分枚举最大生成树】or【最小最大 生成树】

这样阴沉的天气持续下去，我们不免担心起他的健康。

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，表示符合条件的魔法阵的魔力值之和。
Sample Input
4 6
1 2 3
1 3 1
1 4 7
2 3 4
2 4 5
3 4 6
Sample Output
12
我的做法，用二分枚举边权，建立最大生成树。
代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define LL long long
using namespace std;
const int MAXN = 1e5+100;
const int MAXM = 1e6+100;
/*---------------------------*/
struct Edge {int from,to,val;
}edge[MAXM];
int n,m;
int par[MAXN];
void init(){
   for(int i=0;i<=n;i++) par[i]=i;}
bool cmp(Edge a,Edge b){
   return a.val>b.val ; };
int Find(int x){
   return x==par[x]?x:par[x]=Find(par[x]);}
void join(int a,int b){a=Find(a);b=Find(b);par[a]=b;}
LL f(int  x){init();int num=0;LL ans=0;for(int i=1;i<=m;i++){Edge e=edge[i];if(e.val<=x&&Find(e.from)!=Find(e.to)){num++;ans+=(LL)e.val;join(e.from,e.to);}}return num==n-1?ans:(LL)0;
}
void MST(){LL le=1;LL ri=-1;for(int i=1;i<=m;i++) {scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].val);ri=max(ri,(LL)edge[i].val);}sort(edge+1,edge+m+1,cmp);LL mid;//printf("%lld %lld\n",le,ri);LL sum=0;while(le<=ri){LL temp;mid=(ri+le)>>1;if(temp=f(mid)) {ri=mid-1;sum=temp;}else le=mid+1;}printf("%lld\n",sum);
}
int main(){scanf("%d%d",&n,&m);MST();return 0;
}

还有一种直接的做法 就是先求一次最小生成树，找到最大边权，以这个边为边界，求一次最大生成树 。
代码

#include <iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define LL long long
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){
   if(ch=='-' )f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;
}
/*----------------------------------*/
const int MAXN = 1E5+100;struct Edge {int from,to,val;
}edge[MAXN<<2];
bool cmp(Edge a,Edge b){return a.val<b.val;
}
int par[MAXN];
int n,m;
void init(){
   for(int i=0;i<=n;i++) par[i]=i;}
int Find(int x){int r=x;while(r==par[r]) return r;while(r!=par[r]) r=par[r];int j=x;while(j!=r){int k=par[j];par[j]=r;j=k;}return r;
}
void join(int a,int b){a=Find(a);b=Find(b);if(a!=b) par[a]=b;
}
void getmap(){int a,b,c;for(int i=0;i<m;i++){a=read();b=read();c=read();edge[i]={a,b,c};}
}
void MST(){int num=0;sort(edge,edge+m,cmp);init();LL MAX=-1;for(int i=0;i<m;i++){Edge e=edge[i];if(Find(e.from)!=Find(e.to)){num++;join(e.from,e.to);MAX=max(MAX,(LL)e.val); //因为可能有边长相等的边，所以只能找到最大的边的大小，而不能找到其位置。}}init();LL sum=0;num=0;for(int i=m-1;i>=0;i--){Edge e=edge[i];if(Find(e.from)!=Find(e.to)&&e.val<=MAX){num++;sum+=(LL)e.val;join(e.from,e.to);if(num==n-1) break;}}printf("%lld\n",sum);
}int main()
{cin>>n>>m;getmap();MST();return 0;
}