洛谷 UVA1395 苗条的生成树 Slim Span

题目链接

题目描述

求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

题目分析

要求所有生成树中边权极差最小值，起初令人无从下手。但既然要求所有生成树中边权极差最小值，我们自然需要对每一棵生成树都进行考虑，而我们又显然不可能枚举所有生成树，那么首先要解决的就是求在某一条件下某一棵生成树上的边权极差最小值。

我们试着把这个条件具体化，比如说固定一条边，为了方便，我们假定这条边是树中的最小边，也就是要在拥有同样的最小边的生成树中求边权极差最小值。这个问题很好解决。这些生成树中，因为最小的边固定，那么我们尽量让最大边最小，就能够使得边权的极差最小。而要让最大边最小的生成树，其实也就是以我们固定的这条边为最小边的最小生成树。

于是这道题的解法就清楚了——枚举每一条边，求以它为最小边的最小生成树的边权极差，并从中求取最小值。需要注意的是，并非以每一条边为最小边都能够构建一棵最小生成树，因此我们需要判断是否形成了树，如果是再进行比较。

代码

 1 #include<algorithm>
 2 #include<cstdio>
 3 using namespace std;
 4 struct edge
 5 {
 6     int u,v,w;
 7     friend bool operator <(const edge &t1,const edge &t2)
 8     {
 9         return t1.w<t2.w;
10     }
11 }a[5001];
12 int n,m,minn,total,father[5001],tree[100];
13 bool vis[5001],check;
14 int find(int x)
15 {
16     if(father[x]!=x)
17         father[x]=find(father[x]);
18     return father[x];
19 }
20 void merge(int x,int y)
21 {
22     x=find(x);
23     y=find(y);
24     father[x]=y;
25     return;
26 }
27 int main()
28 {
29     while(scanf("%d%d",&n,&m)!=EOF)
30     {
31         if(!n&&!m)
32             break;
33         check=false;
34         minn=0x7fffffff;
35         for(int i=1;i<=m;++i)
36             scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
37         sort(a+1,a+m+1);
38         for(int k=1;k<=m;++k)
39         {
40             total=0;
41             for(int i=1;i<=m;++i)
42                 father[i]=i;
43             for(int i=k;i<=m;++i)
44             {
45                 if(find(a[i].u)!=find(a[i].v))
46                 {
47                     tree[++total]=i;
48                     merge(a[i].u,a[i].v);
49                     if(total==n-1)
50                         break;
51                 }
52             }
53             if(total==n-1)
54             {
55                 check=true;
56                 minn=min(a[tree[total]].w-a[tree[1]].w,minn);
57             }
58         }
59         if(!check)
60             puts("-1");
61         else
62             printf("%d
",minn);
63     }
64     return 0;
65 }

Slim Span