uva 1395

求图上苗条度（最大边 - 最小边) 最小的生成树

像kruskal 一样，给边排序，枚举L,R 区间，更新答案

#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 1395所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。