【uva 1395】Slim Span（图论--最小生成树+结构体快速赋值模版题）

2023-09-16 阅读 25 评论 0

摘要：题意：给一个N(N<=100)个点的联通图（无自环和平行边），求苗条度（最大边-最小边的值）尽量小的生成树。解法：枚举+Kruskal。先从小到大排序边，枚举选择的最小的边。 1 #include<cstdio> 2 #include<

题意：给一个N(N<=100)个点的联通图（无自环和平行边），求苗条度（最大边-最小边的值）尽量小的生成树。

解法：枚举+Kruskal。先从小到大排序边，枚举选择的最小的边。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7 const int N=110,M=5010,D=10010;
 8 
 9 struct node
10 {
11     int x,y,d;
12     node() {}
13     node(int x,int y,int d):x(x),y(y),d(d) {}
14     //bool operator < (const node& now) const
15     //{  return d<now.d;  }
16 };
17 node a[M];
18 int fa[N];
19 int n,m;
20 
21 bool cmp(node x,node y) {return x.d<y.d;}
22 int mmin(int x,int y) {return x<y?x:y;}
23 int ffind(int x)
24 {
25     if (fa[x]!=x) fa[x]=ffind(fa[x]);
26     return fa[x];
27 }
28 int Kruskal()
29 {
30     int i,j,k;
31     int x,y,xx,yy;
32     int cnt,ans=D;
33     sort(a+1,a+1+m,cmp);
34     for (i=1;i<=m;i++)
35     {
36       for (j=1;j<=n;j++) fa[j]=j;
37       cnt=0;
38       for (j=i;j<=m;j++)
39       {
40         x=a[j].x,xx=ffind(x);
41         y=a[j].y,yy=ffind(y);
42         if (xx!=yy)
43         {
44           cnt++;
45           fa[xx]=yy;
46           if (cnt==n-1) {ans=mmin(ans,a[j].d-a[i].d);break;}
47         }
48       }
49     }
50     if (ans==D) ans=-1;
51     return ans;
52 }
53 int main()
54 {
55     while (1)
56     {
57       scanf("%d%d",&n,&m);
58       if (!n&&!m) break;
59       int i,x,y,d;
60       for (i=1;i<=m;i++)
61       {
62         scanf("%d%d%d",&x,&y,&d);
63         a[i]=node(x,y,d);
64       }
65       printf("%d\n",Kruskal());
66     }
67     return 0;
68 }