并查集|poj3522解题报告
题目大意：题意：给点一个无向图，求一个生成树使树中最大边与最小边的差的最小。
解题思路；首先按照边权排一次序，然后依次枚举最小的边权，利用kruskal算法生成无根树！！！（利用并查集维护集合关系）
【并查集|poj3522解题报告】#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e4;
const int INF=(1<<30);
int p[maxn],n,m,u,v,d;
struct Edge {
int u, v, d;
Edge(int u, int v, int d):u(u),v(v),d(d) {}
bool operator < (const Edge& rhs) const {
return d < rhs.d;
}
};
void Make_Set(int n)
{
for(int i=1;
i<=n;
i++)
p[i]=i;
}
int Find_Set(int x)
{
return p[x] != x ? p[x] = Find_Set(p[x]) : x;
}
vector
int main()
{
//freopen("1.txt","r",stdin);
while(scanf("%d%d",&n,&m)==2)
{
e.clear();
if(m==0&&n==0)break;
for(int i=0;
i
scanf("%d%d%d",&u,&v,&d);
e.push_back(Edge(u,v,d));
}
sort(e.begin(),e.end());
int ans=INF;
for(int L=0;
L
Make_Set(n);
int cnt=0;
for(int R=L;
R
int u=Find_Set(e[R].u);
int v=Find_Set(e[R].v);
if(u!=v)
{
p[u]=v;
cnt++;
if(cnt==n-1){ans=min(ans,e[R].d-e[L].d);
break;
}
}
}
}
if(ans==INF)printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}
推荐阅读
- 抱怨并没有任何意义
- 读猫文收获
- 喜剧演员，小丑一样的活着
- 如果鸽子会说话（二十三）
- 排序（归并排序）
- 逃避问题并不能让问题消失
- 羁旅.和陆游临安春雨初霁并步原韵（旧体诗）
- 【剽悍晨读感悟】0714并不是要把一天过成48小时的样子
- 用npm发布一个包的教程并编写一个vue的插件发布
- 来日方长并不长