解题步骤:
1. 首先用深搜,判断环路;
2 再用一次深搜,找出最大直径;
注意点:
1. 数据范围较大,用递归会爆栈,得手动开栈
#pragma comment(linker, "/STACK:102400000,102400000")
2.每个节点只用保存两个变量:max:以该节点为根节点,的最大直径; max_len:以该节点为根节点的最长孩子深度;
最大max:if((temp = node[edge[i].node].max_len + edge[i].len + node[root].max_len) > node[root].max)
node[root].max = temp;
最大max_len: if(temp > node[root].max_len)
node[root].max_len = temp;
#pragma comment(linker, "/STACK:102400000,102400000") #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXE 2000005 #define MAXN 100005 struct Edge{ int node; int next; int len; }edge[MAXE]; struct Node{ int max; int max_len; }node[MAXN]; int head[MAXN], cnt; void add(int a, int b, int c) { edge[cnt].node = b; edge[cnt].len = c; edge[cnt].next = head[a]; head[a] = cnt ++; edge[cnt].node = a; edge[cnt].len = c; edge[cnt].next = head[b]; head[b] = cnt ++; } bool vis[MAXN]; bool dfs(int root, int fa) { vis[root] = 1; for(int i = head[root]; ~i; i = edge[i].next) { if(edge[i].node != fa) { if(vis[edge[i].node]) return 0; if(dfs(edge[i].node, root) == 0) return 0; } } return 1; } int max; int dp(int root, int fa) { vis[root] = 0; node[root].max_len = node[root].max = 0; for(int i = head[root]; ~i; i = edge[i].next) { if(edge[i].node != fa) { dp(edge[i].node, root); int temp; if((temp = node[edge[i].node].max_len + edge[i].len + node[root].max_len) > node[root].max) node[root].max = temp; if(temp > node[root].max_len) node[root].max_len = temp; } } if(node[root].max > max) max = node[root].max; return 0; } int main() { int n, m; while(~scanf("%d%d", &n, &m)) { memset(head, -1, sizeof(head)); cnt = 0; while(m--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } memset(vis, 0, sizeof(vis)); int i; for(i = 1; i <= n; ++i) { if(!vis[i]) { if(!dfs(i, -1)) break; } } if(i <= n) printf("YES\n"); else { for(int i = 1; i <= n; ++i) { if(vis[i]) dp(i, -1); } printf("%d\n", max); } } return 0; }