树的专题整理(二)

树的专题整理(二)

大家好,又见面了,我是全栈君。

    

 这一篇博客继续以一些OJ上的题目为载体,对树专题进行整理整理一下。

会陆续的更新。。。

这是树的专题整理的第二篇博客,假设第一篇博客的地址在:http://blog.csdn.net/hjd_love_zzt/article/details/29401743


例题:

1、POJ 2485

题目与分析:

这道题抽象一下:“是求最小生成树的最大边”


2)使用kruscal算法来解决

/*
 * POJ_2485_kruscal.cpp
 *
 *  Created on: 2014年6月11日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 505;
const int maxm = maxn*maxn;
const int inf = 9999999;

int map[maxn][maxn];
int father[maxn];
int find(int x) {
	if (x == father[x]) {
		return x;
	}

	father[x] = find(father[x]);
	return father[x];
}

void merge(int x, int y) {
	int fx = find(x);
	int fy = find(y);

	if (fx != fy) {
		father[fx] = fy;
	}
}


struct Edge{
	int begin;
	int end;
	int weight;
	int selected;
}edge[maxm];

bool cmp(Edge a,Edge b){
	if(a.weight != b.weight){
		return a.weight < b.weight;
	}

	if(a.begin < b.begin){
		return a.begin < b.begin;
	}

	return a.end < b.end;
}

int n,m;

int maxe;

int kruscal(){
	int sum = 0;

	int i;
	for(i = 1 ; i <= n ; ++i){
		father[i] = i;
	}

	sort(edge+1,edge+1+m,cmp);

	int k = 0;
	for(i = 1 ; i <= m ; ++i){
		if( k == n-1){
			break;
		}

		int x = find(edge[i].begin);
		int y = find(edge[i].end);
		if(x != y){
			merge(x,y);
			k++;
			edge[i].selected = true;

			sum += edge[i].weight;

			maxe = edge[i].weight;//用来记录最下生成树中当前的最大边
		}
	}

	return sum;
}


int main(){
	int t;
	scanf("%d",&t);

	while(t--){
		scanf("%d",&n);
		m = 1;

		int i;
		int j;
		for(i = 1 ; i <= n ; ++i){
			for(j = 1 ; j <= n ; ++j){
				scanf("%d",&map[i][j]);
			}
		}


		for(i = 1 ; i <= n ; ++i){
			for(j = i+1; j <= n ; ++j){
				edge[m].begin = i;
				edge[m].end = j;
				edge[m].weight = map[i][j];
				edge[m++].selected = false;
			}
		}

		kruscal();



		printf("%d\n",maxe);

	}

	return 0;
}












版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115547.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • shell中if elif_shell编程if语句格式

    shell中if elif_shell编程if语句格式测试shell脚本编程时,写了如下代码:在对if-elif-else分支进行数值判断时,发现一个奇怪的现象:如果使用testconditon(即[condition])进行判定,当第一条if条件为假时,无论代码中的elif语句条件是否为真,都输出elif分支下的语句;查看输出结果,发现输出结果显然与期望值不一样为了能够得到预期结果,发现如果采用双圆括号是进行判断,可得到预期结…

  • git fetch 和git pull 的差别

    git fetch 和git pull 的差别

  • 基于Opencv快速实现人脸识别(完整版)

    基于Opencv快速实现人脸识别(完整版)上篇博客:https://blog.csdn.net/beyond9305/article/details/92844258严格来说标题是有误的,只是单纯地对人脸进行了检测,而并非识别,opencv内置了检测分类器和识别器,这二者还是有很大不同的。这次进一步地研究这一块的知识,来一波真正意义上的人脸识别,查询的资料可能有点过时,但基本思想是没有毛病的,对一些函数也进行了更新,保证了功能的正常实…

  • pycharm2020.3.4安装教程_python安装pycharm的方法

    pycharm2020.3.4安装教程_python安装pycharm的方法Pycharm2020安装及使用和python3.9的安装以及使用python3.9环境安装及使用python下载:推荐网址:https://www.python.org/getit/建议:在官网上下载python,在其它下载,一般是有捆绑软件python安装打开界面,选上ADDpython3.9topath,就是吧python环境变量加到电脑上。​2.我这里卸载后在安装的​3.这里可以更改软件路径,建议像我这样勾4.安装成

  • intercept用法_俄大使称加拿大新制裁仅具象征性

    intercept用法_俄大使称加拿大新制裁仅具象征性“斜率”参数(w,也叫作权重或系数)被保存在coef_属性中,而偏移或截距(b)被保存在intercept_属性中L1正则化时,可以通过coef_中不等于0的个数来确定使用了几个特征np.sum(lasso.coef_!=0)…

  • eureka本地集群配置eureka集群

    eureka本地集群配置eureka集群eureka本地集群配置eureka集群server:port:4000spring:application:name:eurkea-servereureka:server:enable-self-preservation:false#关闭自我保护(缺省为打开)eviction-interval-timer-in-ms:5000#扫描失效服务的间隔时间(缺省为60*1000ms)client:

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号