1395

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<vector>
 5 #include<map>
 6 #include<set>
 7 #include<cstring>
 8 #include<cstdio>
 9 #include<cmath>
10 #include<cstdlib>
11 #include<stack>
12 #include<iomanip>
13 #include<cctype>
14 #include<climits>
15 #include<queue>
16 #define INF 10001
17 using namespace std;
18 typedef long long ll;
19 typedef unsigned long long ull;
20 
21 const int maxn=5000;
22 int u[maxn],v[maxn],fa[maxn],r[maxn],w[maxn];
23 
24 int find(int x)
25 {
26     return fa[x]==x?x:fa[x]=find(fa[x]);
27 }
28 
29 int cmp(int i,int j)
30 {
31     return w[i]<w[j];
32 }
33 
34 void Kruskal(int m,int n)
35 {
36     int ans=INF;
37     for(int i=1;i<=m;i++)
38         r[i]=i;
39     sort(r+1,r+m+1,cmp);
40     for(int i=1;i<=m;i++){
41         for(int j=1;j<=n;j++)
42             fa[j]=j;
43         int node=0,temp=0;
44         for(int k=i;k<=m;k++){
45             int e=r[k];
46             int x=find(u[e]);
47             int y=find(v[e]);
48             if(x!=y){
49                 fa[x]=y;
50                 node++;
51                 if(node==n-1){//题目已经说明G是一个连通图，所以当所有节点都访问到时，说明走成了一条通路，于是可以计算这条通路的苗条度。
52                     temp=w[r[k]]-w[r[i]];
53                     ans=min(ans,temp);
54                     break;
55                 }
56             }
57         }
58     }
59     if(ans!=INF)
60         printf("%d
",ans);
61     else
62         printf("-1
");
63 }  
64 
65 
66 int main()
67 {
68     int m,n;
69     while(~scanf("%d %d",&n,&m)){
70         if(n==0&&m==0)
71             return 0;
72         for(int i=1;i<=m;i++)
73             scanf("%d%d%d",&u[i],&v[i],&w[i]); 
74         Kruskal(m,n);
75     }
76     return 0;
77 }
做题笔记，只是想积累看看四年之后写了AC了多少题。