51nod 1640最小生成树最大生成树

本文主要是介绍51nod 1640最小生成树最大生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：首先对全图求一次最小生成树，最出来生成树的自大边便是所有情况中最小的（因为kruscal和prime每次选边都是选从小选到大），然后再从最大的边从大到小开始枚举最大生成树，求出权值和即可。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=3e5+50;
int n,m,u,v,w,r[maxn],fa[maxn],t,max_edge;
long long cost;struct edge{int from,to,weight;
}e[maxn];bool cmp_min(edge a,edge b){return a.weight<b.weight;
}bool cmp_max(edge a,edge b){return a.weight>b.weight;
}void init(){cost=0;memset(r,0,sizeof(r));for(int i=1;i<=n;i++)fa[i]=i;
}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}void unite(int a,int b){a=find(a);b=find(b);if(a==b) return;if(r[a]>r[b]) fa[b]=a;else{fa[a]=b;if(r[a]==r[b]) r[a]++;}
}void MIN(){init();sort(e+1,e+1+m,cmp_min);for(int i=1;i<=m;i++){if(find(e[i].from)!=find(e[i].to)){unite(e[i].from,e[i].to);max_edge=max(max_edge,e[i].weight);}}
}long long MAX(){init();sort(e+1,e+1+m,cmp_max);for(int i=1;i<=m;i++){if(e[i].weight>max_edge) continue;if(find(e[i].to)!=find(e[i].from)){unite(e[i].to,e[i].from);cost+=e[i].weight;}}return cost;
}int main(){//freopen("out.txt","w",stdout);while(scanf("%d%d",&n,&m)!=EOF){memset(e,0,sizeof(e));max_edge=0;for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].weight);MIN();printf("%lld\n",MAX());}return 0;
}

这篇关于51nod 1640最小生成树最大生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---