首页 > 代码库 > 【最小生成树】【kruscal】【贪心】CDOJ1636 梦后楼台高锁，酒醒帘幕低垂
【最小生成树】【kruscal】【贪心】CDOJ1636 梦后楼台高锁，酒醒帘幕低垂
给你一个有n个点和m条边的无向连通图,每条边都有一个权值ww.
我们定义，对于一条路径，它的Charm value为该路径上所有边的权值的最大值与最小值的差.
询问从1到n的所有路径的Charm value的最小值.
首先，考虑到，我们需要找到一条路径，使它的最小边尽量大，最大边尽量小
然后，考虑到m比较小，我们可以去寻找一个m^2或者m^2logm的算法
考虑枚举最小边，那么我们就需要在m或者mlogm的时间内找到尽量小的最大边
回忆最小生成树的kruskal算法，并查集+贪心加边
应用到此题，从枚举的最小边贪心加边，当1和n属于同一个集合时停止，得出的一定是当前最小边情况下的最优解
#include<cstdio>
#include<algorithm>
using namespace std;
int fa[210];
int find(int x){
return x==fa[x] ? x : fa[x]=find(fa[x]);
}
struct Edge{
int u,v,w;
}es[1010];
bool cmp(const Edge &a,const Edge &b){
return a.w<b.w;
}
int n,m,ans=2147483647;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].w);
}
sort(es+1,es+m+1,cmp);
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
fa[j]=j;
}
bool flag=0;
for(int j=i;j<=m;++j){
int U=find(es[j].u),V=find(es[j].v);
if(U!=V){
fa[U]=V;
}
if(find(1)==find(n)){
flag=1;
ans=min(ans,es[j].w-es[i].w);
break;
}
}
if(!flag){
break;
}
}
printf("%d\n",ans);
return 0;
}
【最小生成树】【kruscal】【贪心】CDOJ1636 梦后楼台高锁，酒醒帘幕低垂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。