头部背景图片
Decaku 's Blog |
Decaku 's Blog |

Poj 3522 Slim Span

描述:

找一棵生成树,且生成树中边权最大差值尽可能小。


思路:

$把边权从小到大排序,然后依次枚举生成树中的最小权重,更新差值, \\
找到答案,算法复杂度为E*log(V)*E。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;
int p[105];
int Find(int x)
{
return p[x]==x?x:p[x]=Find(p[x]);
}
void join(int x,int y)
{
int px=Find(x),py=Find(y);
if(px!=py)
p[px]=py;
}
struct node
{
int u,v,w;
} e[6000];
bool cmp(node x,node y)
{
return x.w<y.w;
}

int main()
{
int n,m,t;
bool flag;
while(cin>>n>>m&&(n+m))
{
for(int i=1; i<=m; i++)
{
cin>>e[i].u>>e[i].v>>e[i].w;
}
sort(e+1,e+m+1,cmp);
flag=false;
int ans=1e7;
for(int i=1; i<=m; i++)
{
t=0;
int tem;
for(int k=0; k<105; k++)
p[k]=k;
for(int j=i; j<=m&&t<n-1; j++)
{
int x=Find(e[j].u);
int y=Find(e[j].v);
if(x!=y)
{
p[x]=y;
t++;
tem=j;
}
}
if(t==n-1)
{
flag=true;
ans=min(ans,e[tem].w-e[i].w);
}
}
if(flag)
cout<<ans<<endl;
else cout<<-1<<endl;
}
}
avatar Decaku 菜菜菜