文章

25

粉丝

0

获赞

0

访问

68525

头像
树的直径
经验总结
发布于2020年4月14日 21:04
阅读数 2959

树的直径:树中所有最短路径的最大值。(1)树状dp(得到直径值);(2)若无负权边,2次DFS(BFS)得到直径值和最长链)

(1)在一个连通无向无环图中,以任意结点出发所能到达的最远结点,一定是该图直径的端点之一。

(2)树的直径,等于以树直径上任意一点为根的有根树,其左子树的高度+1,再加上其右子树高度+1。

dfs:

#include<iostream>
using namespace std;
const int N = 1010;
int h[N], next_pos[N], e[N], w[N], n, m, ans, p, idx;
int d[N];//d[i]表示从起点到i点的最长距离
void add(int a, int b, int c){
	e[++idx] = b;
	w[idx] = c;
	next_pos[idx] = h[a];
	h[a] = idx;
}

void dfs(int x, int father){
	if (ans < d[x]){
		ans = d[x];
		p = x;
	}
	for (int i = h[x]; i; i = next_pos[i]){
		int j = e[i];
		if (j == father){ continue; }
		d[j] = d[x] + w[i];
		dfs(j, x);
	}
}

void find(int x){
	ans = 0;
	d[x] = 0;
	dfs(x, 0);
}

int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
		add(y, x, w);
	}

	find(1);
	find(p);
	cout << ans << endl;
	
	return 0;
}

(2)树状dp

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m, h[N], next_pos[N], w[N], e[N], idx, ans;
int first_max[N], second_max[N];
void add(int a, int b, int c){
	e[++idx] = b;
	w[idx] = c;
	next_pos[idx] = h[a];
	h[a] = idx;
}

void dp(int x, int father){
	for (int i = h[x]; i; i = next_pos[i]){
		int j = e[i];
		if (j == father){ continue; }
		dp(j, x);
		if (first_max[x] < first_max[j] + w[i]){
			second_max[x] = first_max[x];
			first_max[x] = first_max[j] + w[i];
		}
		else if (second_max[x] < first_max[j] + w[i]){
			second_max[x] = first_max[j] + w[i];
		}
		ans = max(ans, first_max[x] + second_max[x]);
	}
}

int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
		add(y, x, w);
	}

	dp(1, 0);
	cout << ans << endl;

	return 0;
}

 

 

 

 

 

 

 

 

 

 

 



登录后发布评论

暂无评论,来抢沙发