UVA 1395 Slim Span（MST）
來源：程序員人生 發布時間：2016-12-04 14:04:06 閱讀次數：2423次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
