首页 > 代码库 > 蓝桥杯 大臣的旅费_树的最长度_两次DFS
蓝桥杯 大臣的旅费_树的最长度_两次DFS
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <functional>#include <vector>using namespace std;const int maxn = 1000000 + 10;const int INF = 10000000;int n;bool used[maxn];vector<int> G[maxn];vector<int> E[maxn]; //边 int d[maxn];void init() { memset(used, 0, sizeof(used));}void dfs(int u){ used[u] = true; int size = G[u].size(); for (int i = 0; i < size; i++) { int v = G[u][i]; //得到这个点的临边 if (!used[v]) { d[v] = d[u] + E[u][i]; //走临边的情况 dfs(v); //dfs()临边 } }}void solve(){ cin >> n; int u, v, w; for (int i = 0; i < n - 1; i++) { scanf("%d%d%d", &u, &v, &w); G[u - 1].push_back(v - 1); E[u - 1].push_back(w); G[v - 1].push_back(u - 1); E[v - 1].push_back(w); } //第一遍 init(); fill(d, d + n, INF); d[0] = 0; //递归找到最远路 dfs(0); int start = 0; //得到最大值的下标 int max = -1; //为了找到最远路 for (int i = 0; i < n; i++) { if (d[i] > max && d[i] != INF) { //走过 max = d[i]; start = i; //找到最远路 } } //http://blog.csdn.net/chao1983210400/article/details/26447001 //树的最长路求法:两次dfs,从任意点出发一次dfs找到的最远结点A,再从A开始进行一次dfs找到的最远点既为树的的直径。 //第二遍 //从最远路出发,dfs找到的最远点一定是树的直径 //现有结论,从任意一点u出发搜到的最远的点一定是s、t中的一点,然后在从这个最远点开始搜,就可以搜到另一个最长路的端点, //即用两遍广搜就可以找出树的最长路 init(); for (int i = 0; i < n; i++) { d[i] = (i == start ? 0 : INF); } dfs(start); int ans = -1; for (int i = 0; i < n; i++) { if (d[i] > ans && d[i] != INF) { ans = d[i]; } } ans = 10 * ans + ans * (ans + 1) / 2; cout << ans << endl; }int main(){ solve(); return 0;}
蓝桥杯 大臣的旅费_树的最长度_两次DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。