51nod 1640 MST+二分

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=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示例

Output示例

一道最大生成树的题目，对于这个最大魔法链值，我们显然可以通过二分出来他的最小值，然后类似于最小生成树的贪心做法，我们从满足条件的权值最大的边开始运行kruskal，由于要求只能有N-1条魔法链，所以相当于是kruskal只不过将边倒序枚举。

第一次直接把l=0，r=INT_MAX,结果T了最后一个点，无奈做了一些优化，找到最大最小值赋给l，r然后就A了。

不过后来看别人题解发现好像没人用二分，可以先求一遍kruskal找到最后加入的边的权值，这就使得最大权值最小了，然后在倒序求一遍kruskal，只要当前边权值不大于之前求得的那个值就好啦。

 #include<bits/stdc++.h>   //二分650ms

 using namespace std;

 #define LL long long

 struct Edge

 {

     int u,v,w;

     bool operator<(const Edge &t)const{

     return w<t.w;

     }

 }e[];

 int f[];

 int getf(int v){return f[v]==v?f[v]:f[v]=getf(f[v]);}

 bool ok(int k,int N,int M)

 {

     for(int i=;i<=N;++i) f[i]=i;

     for(int i=;i<M&&e[i].w<=k;i++){

         int fu=getf(e[i].u),fv=getf(e[i].v);

         if(fv!=fu){

             N--;

             f[fv]=fu;

         }

         if(N==) return ;

     }

     return ;

 }

 int main()

 {

     int N,M,i,j,l=,r=;

     cin>>N>>M;

     for(i=;i<M;++i){

         scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

         l=min(l,e[i].w);

         r=max(r,e[i].w);

     }

     sort(e,e+M);

     LL ans=;

     while(l<r){

         int mid=l+((r-l)>>);

         if(ok(mid,N,M)){

            r=mid;

         }

         else{

           l=mid+;

         }

     }

     for(int i=;i<=N;++i) f[i]=i;

     Edge e1{-,-,l};

     int ed=upper_bound(e,e+M+,e1)-e;

     for(int i=ed;i>=;--i){

         if(e[i].w>l) continue;

         int fu=getf(e[i].u),fv=getf(e[i].v);

         if(fv!=fu){

             ans+=e[i].w;

             N--;

             f[fv]=fu;

         }

         if(N==) break;

     }

     printf("%lld\n",ans);

     return ;

 }

 #include<bits/stdc++.h>  //300ms

 using namespace std;

 #define LL long long

 struct Edge

 {

     int u,v,w;

     bool operator<(const Edge &t)const{

     return w<t.w;

     }

 }e[];

 int f[];

 int getf(int v){return f[v]==v?f[v]:f[v]=getf(f[v]);}

 int ok(int k,int N,int M)

 {

     for(int i=;i<=N;++i) f[i]=i;

     for(int i=;i<M;i++){

         int fu=getf(e[i].u),fv=getf(e[i].v);

         if(fv!=fu){

             N--;

             f[fv]=fu;

         }

         if(N==) return i;

     }

     return -;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     int N,M,i,j,l=,r=;

     cin>>N>>M;

     for(i=;i<M;++i){

             cin>>e[i].u>>e[i].v>>e[i].w;

     }

     sort(e,e+M);

     LL ans=;

     l=ok(,N,M);

     while(l<M&&e[l+].w==e[l].w) l++;

     for(int i=;i<=N;++i) f[i]=i;

     for(int i=l;i>=;--i){

         int fu=getf(e[i].u),fv=getf(e[i].v);

         if(fv!=fu){

             ans+=e[i].w;

             N--;

             f[fv]=fu;

         }

         if(N==) break;

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

51nod 1640 MST+二分

最新文章

热门文章