UVA 1395 Slim Span--苗条的生成树（并查集+枚举）

痛定思痛。 2024-02-17 22:09 30阅读 0赞

题意：给出n(n<=100)个结点的图，求苗条度（最大边减最小边的值）尽量小的生成树。

数据量最大为5000，枚举遍历，复杂度m^2。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 100000000
    const int maxn=5000+10;
    int u[maxn],v[maxn],w[maxn];
    int r[maxn];
    int pre[100+5]; 
    int n,m;
    	
    bool cmp(int i,int j){
    	return w[i]<w[j];
    }
    
    int find(int x){
    	return x==pre[x]?x:find(pre[x]);
    }
    
    void init(){
    	for(int i=1;i<=n;i++)
    	pre[i]=i;
    }
    
    int main(){
    	while(scanf("%d%d",&n,&m)==2&&n){
    		for(int i=1;i<=m;i++){
    			scanf("%d%d%d",&u[i],&v[i],&w[i]);
    			r[i]=i;
    		}
    		
    		sort(r+1,r+m+1,cmp);
    		int Min=INF;
    		for(int i=1;i<=m;i++){
    			init();
    			int last;
    			for(int j=i;j<=m;j++){
    				int x=u[r[j]],y=v[r[j]];
    				int fx=find(x),fy=find(y);
    				if(fx!=fy){
    					pre[fx]=fy;
    					last=j;  //找到生成树最后一条边的序号 
    				}
    			}
    			
    			int flag=0;
    			for(int k=2;k<=n;k++){ //判断所有点是否连通 
    				int fx=find(1),fy=find(k);
    				if(fx!=fy){
    					flag=1;
    					break;
    				}
    			}
    			
    			if(!flag)
    			   Min=min(Min,w[r[last]]-w[r[i]]);
    		}
    		if(Min!=INF)printf("%d\n",Min);
    		else printf("-1\n");
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，30人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 1395 Slim Span--苗条的生成树（并查集+枚举）

题意：给出n(n<=100)个结点的图，求苗条度（最大边减最小边的值）尽量小的生成树。数据量最大为5000，枚举遍历，复杂度m^2。 AC代码： include

痛定思痛。/ 2024年02月17日 22:09/ 0 赞/ 31 阅读

相关 codevs1001 舒适的路线贪心枚举+并查集

题目描述 Description Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。 Z小镇附近共有 N(1<N≤500)个景点（编号为1,2,3,…,N

旧城等待，/ 2024年02月17日 19:50/ 0 赞/ 10 阅读

相关并查集&&最小生成树（模板）

并查集 int find(int x){ //查查找根节点 int r=x; while(r!=pre[r]) r

小灰灰/ 2022年08月03日 15:53/ 0 赞/ 158 阅读

相关 POJ 3522-Slim Span（苗条树-kruskal生成树）

Slim Span <table> <tbody> <tr> <td><strong>Time Limit:</strong> 5000MS</t

向右看齐/ 2022年06月16日 03:22/ 0 赞/ 154 阅读

相关 Slim Span UVA - 1395 ——Kruskal算法生成最小树

Think: 1Kruskal算法生成最小树 2题意理解: 1>生成一颗最小树使得他的边的最大权值减去边的最小权值最小 3思路:从权值最小的边出发建立最小生成树

待我称王封你为后i/ 2022年06月15日 06:57/ 0 赞/ 114 阅读

相关 Slim Span

题目链接：[https://vjudge.net/contest/179332\problem/H][https_vjudge.net_contest_179332_probl

「爱情、让人受尽委屈。」/ 2022年06月10日 11:53/ 0 赞/ 132 阅读

相关 POJ 3522 Slim Span（生成树+克鲁斯卡尔）

Given an undirected weighted graph G, you should find one of spanning trees specified as

女爷i/ 2022年06月10日 02:52/ 0 赞/ 139 阅读

相关并查集 +最小生成树

并查集：并查集简单来说就是数据分类，怎么分呢，初始把数组 pre\[i\] = i 设定，表示自己归属于自己，如果A是B的老大，那么pre\[A\] = A， pre\

╰半夏微凉°/ 2022年06月10日 00:07/ 0 赞/ 205 阅读

相关 UVA1395 Slim Span

题目链接：[点我][Link 1] 题意简述求所有生成树中最大边权与最小边权差最小的，输出它们的差值。并查集生成最小生成树，将边按从小到大排序，生成一个树更新一下答

梦里梦外;/ 2022年05月16日 08:42/ 0 赞/ 132 阅读

相关 uva-10282-枚举

[uva-10282-枚举][uva-10282-] 题意:语言翻译, 直接map即可 include "pch.h" include <string>

秒速五厘米/ 2022年01月06日 11:33/ 0 赞/ 142 阅读