首页 > 代码库 > UVa 1395 (最小生成树)
UVa 1395 (最小生成树)
题目链接:http://vjudge.net/problem/41567/origin
本来想着m^2的复杂度撑不住,对于这种擦着边的复杂度就好慌。
首先对所有的边排个序,然后枚举每个可以构成生成树的区间(L,R),取区间里面构成树的边的权值的最小和最大的差值,求最小值即可。
如果已经构成生成树可以break掉优化下。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 5005; 7 struct edge 8 { 9 int u,v,w; 10 }; 11 edge e[maxn]; 12 int pre[105]; 13 int Find(int x) 14 { 15 return pre[x]==x?x:pre[x]=Find(pre[x]); 16 } 17 bool cmp(edge A,edge B) 18 { 19 return A.w<B.w; 20 } 21 int main() 22 { 23 int n,m; 24 while(scanf("%d %d",&n,&m)!=EOF&&(n||m)) 25 { 26 for(int i=1;i<=m;i++) 27 { 28 scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w); 29 } 30 sort(e+1,e+m+1,cmp); 31 int count1 = 1; 32 int ans = 20000; 33 for(int i=1;i<=m;i++) 34 { 35 for(int k=1;k<=n;k++) pre[k] = k; 36 count1 = 1; 37 int minv = 20000; 38 int maxv = 0; 39 for(int j=i;j<=m;j++) 40 { 41 int x = Find(e[j].u); 42 int y = Find(e[j].v); 43 if(x!=y) 44 { 45 count1++; 46 pre[x] = y; 47 maxv = max(maxv,e[j].w); 48 minv = min(minv,e[j].w); 49 } 50 if(count1>=n) 51 { 52 break; 53 } 54 } 55 if(count1>=n) 56 { 57 ans = min(ans,maxv-minv); 58 } 59 } 60 if(ans!=20000) printf("%d\n",ans); 61 else printf("-1\n"); 62 } 63 return 0; 64 }
UVa 1395 (最小生成树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。