树的专题整理(二)

全栈程序员-用户IM • 2022年2月2日下午10:00 • 未分类

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

这一篇博客继续以一些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;
}