题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4514
首先我们要判断一下有没有环的存在,因为图不是连通图(可能有多个树),所以要对每个点都判断一下是否遍历过,判环的过程就是dfs判断是否存在冲突的情况,然后就是求树的直径,因为图不是连通图,所以对于每一棵树求一个直径取最大值就好了。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 110005
#define maxm 1100005
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
int to,next,w;
}Edge[maxm*2];
int head[maxn],num;
int dist[maxn];
bool vis[maxn], flag, used[maxn];
int n,m;
void init(){
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
num = 0;
}
void add(int u,int v,int w){
Edge[num].to = v;
Edge[num].w = w;
Edge[num].next = head[u];
head[u] = num ++;
}
void dfs(int u,int p){
vis[u] = true;
if(flag) return ;
for(int i=head[u];i!=-1;i=Edge[i].next){
int to = Edge[i].to;
if(!vis[to]) dfs(to, u);
else if(to != p){
flag = true;
return ;
}
}
}
void bfs(int x){
queue<int> q;
memset(dist,0,sizeof(dist));
memset(used,false,sizeof(used));
q.push(x);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = true;
for(int i=head[u];i!=-1;i=Edge[i].next){
int to = Edge[i].to;
if(used[to] == false){
used[to] = true;
dist[to] = dist[u] + Edge[i].w;
q.push(to);
}
}
}
}
int solve(int s){
int Max = 0, pos = s;
bfs(s);
for(int i=1;i<=n;i++){
if(Max < dist[i]){
Max = dist[i];
pos = i;
}
}
bfs(pos);
Max = 0;
for(int i=1;i<=n;i++) Max = max(Max, dist[i]);
return Max;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
init();
for(int i=0;i<m;i++){
int u, v, w;
scanf("%d%d%d",&u,&v,&w);
add(u, v, w);
add(v, u, w);
}
flag = false;
for(int i=1;i<=n;i++){
if(!vis[i]) dfs(i, 0);
}
if(flag){
puts("YES");
continue;
}
int ans = 0;
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++){
if(!vis[i]){
ans = max(ans, solve(i));
}
}
printf("%d\n", ans);
}
return 0;
}