MENU

树的直径模板

2019-06-29 • 阅读: 21 • 常用模板图论—树的直径阅读设置

方法一:树形DP

void dp(int u,int pre)
{
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to, w = edge[i].w;
		if (v == pre) continue;
		dp(v, u);
		ans = max(ans, dis[u] + dis[v] + w);//之前的最大值dis[u],当前的dis[v]+w
		dis[u] = max(dis[u], dis[v] + w);//更新最大距离
	}
}

方法二:两次DFS

第一次BFS找到直径的一端,第二次从直径的一端找到直径的另一端,最终ans即为答案

void dfs(int u, int pre)
{
	if (ans < dis[u]){
		ans = dis[u];
		pos = u;
	}
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to, w = edge[i].w;
		if (v == pre) continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}
	dfs(1, -1);
	dis[pos] = 0;
	dfs(pos, -1);

方法三:两次BFS

void bfs(int st)
{
	memset(vis, false, sizeof(vis));
	vis[st] = true;
	queue<int> q;
	dis[st] = 0;
	q.push(st);
	int pre = -1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to, w = edge[i].w;
			if (!vis[v])
			{
				vis[v] = true;
				dis[v] = dis[u] + w;
				if (ans < dis[v]){
					ans = dis[v];
					pos = v;
				}
				q.push(v);
			}
		}
	}
}

	dis[pos] = 0;
	bfs(pos);

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码