题目大意

给一颗n个点的树，求树的直径（最长的一条链）

题解

先随便找一个点u，dfs出离它最远的点v

于是有以下情况：

直径就是这条链
直径经过u，是这条链的延长
直径不经过u

只需要从v再进行一边dfs，便可以求出直径。

code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

int n, m;

int adj[50005], nxt[100005], go[100005], len[100005], ecnt;

long long dist[50005];

inline void addEdge(int u, int v, int w){

	nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, len[ecnt] = w;

	nxt[++ecnt] = adj[v], adj[v] = ecnt, go[ecnt] = u, len[ecnt] = w;

}

inline void dfs(int u, int f){

	for(int e = adj[u]; e; e = nxt[e]){

		int v = go[e];

		if(v == f) continue;

		dist[v] = dist[u] + len[e];

		dfs(v, u);

	}

}

int main(){

	freopen("h.in", "r", stdin);

	while(~scanf("%d%d", &n, &m)){

		ecnt = 0;

		memset(adj, 0, sizeof adj);

		for(int i = 1; i <= m; i++){

			int u, v, w; char ch;

			scanf("%d %d %d %c", &u, &v, &w, &ch);

			addEdge(u, v, w);

		}

		int v; long long ret = 0;

		dist[1] = 0;

		dfs(1, 0);

		for(int i = 1; i <= n; i++)

			if(ret < dist[i]) ret = dist[i], v = i;

		dist[v] = ret = 0;

		dfs(v, 0);

		for(int i = 1; i <= n; i++)

			if(ret < dist[i]) ret = dist[i], v = i;

		printf("%lld\n", ret);

	}

}

巴特西

POJ 1985 - 树的直径

题目大意

题解

code

最新文章

热门文章