UVA 1395 Slim Span（MST）
发布时间：2020-12-13 21:17:08 所属栏目：PHP教程 来源：网络整理
导读：http://vjudge.net/problem/UVA⑴395 题目大意：让求最小生成树满足修长度最小的条件（修长度：最大边与最小边的差） 思路：在书上。根据Kruskal的思想，当所有点连通了就停止枚举左侧界，记录最小修长度。紫书的代码好稠 #includeiostream#includecstdio#in
|
http://vjudge.net/problem/UVA⑴395 题目大意：让求最小生成树满足修长度最小的条件（修长度：最大边与最小边的差值） 思路：在书上。根据Kruskal的思想，当所有点连通了就停止枚举左侧界，记录最小修长度。紫书的代码好稠 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 105;
struct node
{
int u,v,w;
bool operator < (const node & p)const
{
return w < p.w;
}
}e[N*N];
int n,m,counter;
int f[N];
int getf(int t)
{
if(t != f[t])
f[t] = getf(f[t]);
return f[t];
}
void Init()
{
for(int i = 1;i <= n;i++)
f[i] = i;
counter = 0;
}
int main()
{
while(~scanf("%d%d",&n,&m) && (n || m))
{
for(int i = 1;i <= m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e+1,e+1+m);
int minn = INF;
for(int L = 1;L <= m;L++)
{
Init();
for(int R = L;R <= m;R++)
{
int x = getf(e[R].u);
int y = getf(e[R].v);
if(x != y)
{
f[y] = x;
counter++;
}
if(counter == n⑴)
{
minn = min(minn,e[R].w-e[L].w);
break;
}
}
}
if(minn == INF)
printf("⑴n");
else
printf("%dn",minn);
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |