求图上苗条度(最大边 - 最小边) 最小的生成树
像kruskal 一样,给边排序,枚举L,R 区间,更新答案
复制代码
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#include <iostream> #include <cstring> #include <algorithm> using namespace std ; const int M=1e5; int f[M],n,m,ans; struct E{ int x,y,z; }e[M]; int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } int cmp(E x,E y){ return x.z<y.z; } void krus(){ sort(e+1,e+1+m,cmp); int i,j,x,y,fx,fy,c=0; for(i=1;i<=m;i++){ for(j=1;j<=n;j++) f[j]=j; c=0; for(j=i;j<=m;j++){ x=e[j].x,y=e[j].y,fx=find(x),fy=find(y); if(fx!=fy){ f[fx]=fy; c++; } if(c==n-1){ ans=min(ans,e[j].z-e[i].z);break; } } } } int main(){ //freopen("in","r",stdin); int i,x,y,z; while(cin>>n>>m,n){ for(i=1;i<=m;i++) cin>>e[i].x>>e[i].y>>e[i].z; ans=1<<30,krus(); if(ans!=1<<30) cout<<ans<<endl; else cout<<-1<<endl; } }
最后
以上就是尊敬皮带最近收集整理的关于uva 1395的全部内容,更多相关uva内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复