首页 > 代码库 > poj3522
poj3522
题意:找出一个图的生成树中最大边权值和最小边权值差最小的值。
题解参见:
http://blog.csdn.net/sdj222555/article/details/7698978
每次枚举最小边,然后求生成树,更新结果。
1 //Accepted 200 KB 94 ms 2 //kruskal 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 9 const int MAXN = 105; 10 const int MAXM = MAXN*MAXN; 11 const int inf=10000000; 12 13 int min(int a,int b) 14 { 15 return a>b?b:a; 16 } 17 int max(int a,int b) 18 { 19 return a>b?a:b; 20 } 21 22 struct node 23 { 24 int u,v,c; 25 node(int u,int v,int c):u(u),v(v),c(c) 26 { 27 28 } 29 node() 30 { 31 32 } 33 }p[MAXM]; 34 int e; 35 36 void addnode(int u,int v,int c) 37 { 38 p[e++]=node(u,v,c); 39 } 40 int cmp(node x,node y) 41 { 42 return x.c<y.c; 43 } 44 int f[MAXN]; 45 int n,m; 46 void build() 47 { 48 for (int i=0;i<=n;i++) 49 { 50 f[i]=i; 51 } 52 } 53 int find(int x) 54 { 55 if (x==f[x]) return x; 56 return f[x]=find(f[x]); 57 } 58 void union_set(int x,int y) 59 { 60 int fx=find(x),fy=find(y); 61 if (fx!=fy) 62 { 63 f[fy]=fx; 64 } 65 } 66 void kruskal() 67 { 68 int ans=inf; 69 int cnt; 70 int tmin,tmax; 71 sort(p,p+e,cmp); 72 for (int i=0;i<m;i++) 73 { 74 build(); 75 cnt=0; 76 tmax=-1; 77 tmin=inf; 78 for (int j=i;j<e;j++) 79 { 80 int fx=find(p[j].u); 81 int fy=find(p[j].v); 82 if (fx!=fy) 83 { 84 union_set(fx,fy); 85 tmax=max(tmax,p[j].c); 86 tmin=min(tmin,p[i].c); 87 cnt++; 88 if (cnt==n-1) break; 89 } 90 } 91 if (cnt==n-1) 92 ans=min(ans,tmax-tmin); 93 } 94 if (ans==inf) ans=-1; 95 printf("%d\n",ans); 96 } 97 int main() 98 { 99 while (scanf("%d%d",&n,&m),n+m) 100 { 101 e=0; 102 int u,v,c; 103 for (int i=0;i<m;i++) 104 { 105 scanf("%d%d%d",&u,&v,&c); 106 addnode(u,v,c); 107 } 108 kruskal(); 109 } 110 return 0; 111 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。