UVA 1395 Slim Span（MST）
来源：程序员人生 发布时间：2016-12-04 14:04:06 阅读次数：2216次
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("%d\n",minn);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
