【克鲁斯卡尔蒜法-最小生成树算法】-zzuli-2271 -Problem -E-魔法交流活动

问题 E: 魔法交流活动

题目描述

魔法学校近日开展了主题为“天气晴朗”的魔法交流活动。
N名魔法师按阵法站好，之后选取N - 1条魔法链将所有魔法师的魔力连接起来，形成一个魔法阵。
魔法链是做法成功与否的关键。每一条魔法链都有一个魔力值V，魔法最终的效果取决于阵中所有魔法链的魔力值的和。
由于逆天改命的魔法过于暴力，所以我们要求阵中的魔法链的魔力值最大值尽可能的小，与此同时，魔力值之和要尽可能的大。
现在给定魔法师人数N，魔法链数目M。求此魔法阵的最大效果。

输入

两个正整数N，M。(1 <= N <= 10^5, N <= M <= 2 * 10^5)
接下来M行，每一行有三个整数A, B, V。(1 <= A, B <= N, INT_MIN <= V <= INT_MAX)
保证输入数据合法。

输出

输出一个正整数R，表示符合条件的魔法阵的魔力值之和。

样例输入

样例输出

12
-

大致题意分析：

　　有n个点，选取n-1条边把他们全部连起来形成一棵树，每条边都有一个权值；要求1：所有的边的权值的最大值最小，然后还又要求2：这棵树中的所有的边权值的和最大。

　　思路：这个题目是对边来进行筛选的，需要用克鲁斯卡尔蒜法。这个蒜法是对边来进行操作的，按照边来逐渐形成整棵最小生成树。

具体需要跑两边，第一遍从小到大对边进行一次筛选，筛选出的边的集合可以构成一颗树即可；这是最后一条新加进来的边就是最大的权值maxmin（要求1达成）。

　　　　第二遍，从大到小，具体从等于最小的最大边权值maxlen的边开始跑一遍，直到筛选出的边的集合可以构成一颗树即可，进行筛选、求和，即为最终结果。

ac代码：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <stack>
  7 #include <vector>
  8 #include<math.h>
  9 #include <string.h>
 10 #include<set>
 11 using namespace std;
 12 #define inf 0x7fffffff
 13 #define maxn 10000000
 14 const double pi=acos(-1.0);
 15 #define ll long long
 16 #define N 100008
 17 
 18 int n,m;
 19 struct Edge//存边的结构体
 20 {
 21     int a,b;//两个顶点的编号
 22     ll dis;
 23     Edge(int a=0,int b=0,ll dis=0):a(a),b(b),dis(dis) {}
 24 } edge[N*2];
 25 
 26 int root[N];
 27 
 28 int findroot(int a) //返回点a的根节点，并查集
 29 {
 30     if(root[a]==a)
 31         return a;
 32     return root[a]=findroot(root[a]);
 33 }
 34 int unite(int a,int b) //将a和b节点用并查集的思路连接到一起
 35 {
 36     if(a==b)return 0;//在联通块内部加上的边，及a-b出现在同一个集合内部了
 37     else
 38     {
 39         root[a]=b;
 40         return 1;
 41     }
 42 }
 43 bool cmp(Edge x,Edge y)
 44 {
 45     return x.dis<y.dis;
 46 }
 47 int fact1(int n) //kruscal蒜法调用1次，计算出最小的最大值maxlen
 48 {
 49     for(int i=1; i<=n; i++)
 50         root[i]=i;
 51 
 52     int cnt=0;
 53     ll ans=(ll)inf*(-1);
 54     int i=1;
 55     while(cnt<n-1)//从小到大
 56     {
 57         if(unite(findroot(edge[i].a),findroot(edge[i].b))==1 )
 58         {
 59             cnt++;
 60             ans=max(ans,edge[i].dis);
 61         }
 62         i++;
 63     }
 64     return ans;
 65 }
 66 ll fact2(int n,int maxlen) //kruscal蒜法调用2次，求出在manlen范围下的最小生成树的边集的和
 67 {
 68     for(int i=1; i<=n; i++)
 69         root[i]=i;
 70     int cnt=0;
 71     ll ans=0;
 72     int i=m;
 73     while(cnt<n-1)//从大到小跑边
 74     {
 75         if(edge[i].dis<=(ll)maxlen && unite(findroot(edge[i].a),findroot(edge[i].b))==1 )
 76         {
 77             cnt++;//统计不形成回路的边数，等于n-1时跳出循环
 78             ans+=edge[i].dis;
 79         }
 80         i--;
 81     }
 82     return ans;
 83 }
 84 int main()
 85 {
 86     while(scanf("%d%d",&n,&m)!=EOF)
 87     {
 88 
 89         int x,y;
 90         ll v;
 91         for(int i=1; i<=m; i++)
 92         {
 93             scanf("%d%d%lld",&x,&y,&v);
 94             edge[i]=Edge(x,y,v);//不习惯这种方式可以手动逐一赋值！
 95 
 96         }
 97         sort(edge+1,edge+1+m,cmp);//按边权值升序排列
 98 
 99         int maxlen=fact1(n);//找到合法的最大长度
100 
101         printf("%lld
",fact2(n,maxlen));//求出最终结果
102     }
103 
104     return 0;
105 }

View Code