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    3   5，则最大的边为5

最大生成树的边，分别为：5    4   3，因为6和7这两条边都是大于5的，所以不符合条件

代码如下：

代码一：两个函数写在一起，代码较短

#include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> #define maxn 500000 #define LL long long using namespace std; struct P{ int x,y,v; }a[maxn]; int f[maxn],n,m,s; LL sum; bool cmp1(P a,P b) { return a.v<b.v; } bool cmp2(P a,P b) { return a.v>b.v; } int find(int x) { return f[x]==-1?x:f[x]=find(f[x]); } void f1(int n,int flag) { memset(f,-1,sizeof(f)); if(flag == 1) sort(a+1,a+1+m,cmp1); if(flag == 2) sort(a+1,a+1+m,cmp2); int t=0; for(int i=1;i<=m;i++) { if(flag == 2) if(a[i].v>s) continue; int x=find(a[i].x); int y=find(a[i].y); if(x!=y){ f[x]=y; if(flag == 1) if(a[i].v>s) s=a[i].v; if(flag == 2) sum+=a[i].v; t++; } if(t==n-1) break; } } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].v); s=-1; f1(n,1);///寻找形成最小生成树的最大边 printf("%d\n",s); sum=0; f1(n,2);///构建类似的最大生成树 printf("%lld\n",sum); return 0; } 代码二：分别写两个函数实现最小和最大生成树

#include<stdio.h> #include<string.h> #include<algorithm> #define maxn 500000 #define LL long long using namespace std; struct P{ int x,y,v; }a[maxn]; int r[maxn],f[maxn],n,m,s; bool cmp1(P a,P b) { return a.v<b.v; } bool cmp2(P a,P b) { return a.v>b.v; } int find(int x) { return f[x]==-1?x:f[x]=find(f[x]); } int f1(int n) { int s=-1; memset(f,-1,sizeof(f)); sort(a+1,a+1+m,cmp1); int t=0; for(int i=1;i<=m;i++) { int x=find(a[i].x); int y=find(a[i].y); if(x!=y){ f[x]=y; if(a[i].v>s) s=a[i].v; t++; } if(t==n-1) break; } if(t<n-1) return -1; else return s; } LL f2(int n) { LL sum=0; memset(f,-1,sizeof(f)); sort(a+1,a+1+m,cmp2); int t=0; for(int i=1;i<=m;i++) { if(a[i].v>s) continue; int x=find(a[i].x); int y=find(a[i].y); if(x!=y){ f[x]=y; sum+=a[i].v; t++; } if(t==n-1) break; } if(t<n-1) return -1; else return sum; } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].v); s=f1(n); printf("%lld\n",f2(n)); return 0; }