HDU 4514 湫湫系列故事——设计风景线(无向图判环+树的直径)

题目链接：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;
}