题意有没说清楚的...两点间最多一条路径....
先用并查集检查无向图是否有环...
若干个无环的无向图就是一森林了...
那么题目转化为在一棵树上找最长的路径....绝大部分都是叶子到叶子的距离(除非根节点只有一个孩子..那么最长的可能是根到某个叶子结点)
在森林的每课树上做DP..顺序从叶子到根..
dp[i]..代表i点为根的子树到叶子的最长路径长度....
这题空间上要求较为高...数组尽可能的少开...高效利用空间....
Program:
//http://acm.hdu.edu.cn/showproblem.php?pid=4514
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#define ll long long
#define oo 1000000001
#define MAXN1 1000002
#define MAXN2 100002
using namespace std;
struct node1
{
int y,w,next;
}line[2*MAXN1];
int n,m,father[MAXN2],p[MAXN2],_next[MAXN2],dp[MAXN2]; // p记录每个点的度
queue<int> myqueue;
int getfather(int x)
{
if (father[x]==x) return x;
return father[x]=getfather(father[x]);
}
void doit()
{
int i,x,k,ans;
ans=0;
while (!myqueue.empty()) myqueue.pop();
memset(dp,0,sizeof(dp));
for (i=1;i<=n;i++)
if (p[i]==1) myqueue.push(i);
while (!myqueue.empty())
{
x=myqueue.front();
myqueue.pop();
k=_next[x];
while (k)
{
if (p[line[k].y])
{
p[line[k].y]--;
p[x]--;
if (p[line[k].y]==1) myqueue.push(line[k].y);
if (ans<dp[line[k].y]+dp[x]+line[k].w)
ans=dp[line[k].y]+dp[x]+line[k].w;
if (dp[line[k].y]<dp[x]+line[k].w)
dp[line[k].y]=dp[x]+line[k].w;
}
k=line[k].next;
}
}
printf("%d\n",ans);
return;
}
int main()
{
freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
int x,y,w,i;
bool f;
while (~scanf("%d%d",&n,&m))
{
memset(_next,0,sizeof(_next));
memset(p,0,sizeof(p));
for (i=1;i<=n;i++) father[i]=i;
f=false;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
if (getfather(x)==getfather(y)) f=true;
father[father[x]]=father[y];
line[i*2-1].next=_next[x];
_next[x]=i*2-1;
line[i*2-1].y=y; line[i*2-1].w=w;
line[i*2].next=_next[y];
_next[y]=i*2;
line[i*2].y=x; line[i*2].w=w;
p[x]++,p[y]++;
}
m*=2;
if (f) printf("YES\n");
else doit();
}
return 0;
}