点击打开题目
/************************************************************************************** Date 2018/3/15 19:14 Author Wen Yaxin 解题思路：先用并查集判环，无环的情况下，以某个没有被访问过 的点进行广搜，搜索到距离该点最远的点，在从这个新点开始搜， 搜到最远的点。然后不断比较得到的最远距离实现答案的更新。 变量含义： head:相当于图的链式存储的头节点。 vis:标记某点是否被访问过 f:实现并查集用的集合 dist:存放源点到该点的距离 edge:该数组存放边 方法含义： initSet:初始化集合 findSet:寻找元素所在集合 unionSet:合并集合 addEdge:加边函数 bfs:广搜，求最远的点。 **************************************************************************************/ #include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; const int maxn = 100000+3; const int maxm = 1000000+3; int n,m,cnt,longest,vertex; int head[maxn],vis[maxn],f[maxn],dist[maxn]; struct Edge{ int to; int w; int nex; }edge[maxm*2]; void initSet() { for(int i = 1; i <= n; i++) { f[i] = i; } } int findSet(int x){ while(x != f[x]) { x = f[x]; } return x; } void unionSet(int x,int y) { f[x] = y; } void addEdge(int u,int v,int w) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].nex = head[u]; head[u] = cnt++; edge[cnt].to = u; edge[cnt].w = w; edge[cnt].nex = head[v]; head[v] = cnt++; } void bfs(int x) { int v1,v2; vis[x] = 1; dist[x] = 0; longest = 0; vertex = x; queue<int>qu; qu.push(x); while(!qu.empty()) { v1 = qu.front(); qu.pop(); if(dist[v1]>longest) { longest = dist[v1]; vertex = v1; } for(int i = head[v1]; i != -1; i = edge[i].nex) { v2 = edge[i].to; if(vis[v2] == 0) { vis[v2] = 1; dist[v2] = dist[v1] + edge[i].w; qu.push(v2); } } } } int main() { int u,v,w; while(~scanf("%d%d",&n,&m)) { cnt = 0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); initSet(); bool flag = false; for(int i = 0; i < m; i++) { scanf("%d%d%d",&u,&v,&w); if(!flag) { addEdge(u,v,w); int fu = findSet(u); int fv = findSet(v); if(fu == fv) { flag = true; } else { unionSet(fu,fv); } } } if(flag) { printf("YES\n"); } else { int ans = 0; for(int i = 1; i <= n; i++) { if(vis[i] == 0) { bfs(i); memset(vis,0,sizeof(vis)); bfs(vertex); ans = max(ans,longest); } } printf("%d\n",ans); } } return 0; }