题意与分析

中文题目，木得题意的讲解谢谢。

然后还是分解成两个任务：a)判环，b)找最长边。

对于这样一个无向图，强行转换成负权然后bellman-ford算法求最短是难以实现的，所以感谢没有环——我们可以当作一棵树来做，然后就直接是树的直径的做法了。

这里同之前的题解的思路不一样的是，采用了动态规划的思路来做树的直径。

记\(dp[now][0]\)为从now出发的最长路径，而\(dp[now][1]\)是从now出发的次长路径。

对从now走出来的每条路径都有做一次判断，首先判断它是否比当前最长的路径的长，如果是，那么它变最长当前最长变次长；如果它比最长短（这个很重要，否则会出现最长与次长的节点相重复），那么判断它是否比次长的长，如果是，更新之。

这样，每个过now的最长边就是\(dp[now][0]+dp[now][1]\)，遍历一遍更新之。

值得注意的是，这题没有硬点只有一个连通分量。不要在这边翻车了。

代码

/*

 * Filename: hdu4514.cpp

 * Date: 2018-11-05

 */

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)

#define per(i,a,b) for(repType i=(a); i>=(b); --i)

#define ZERO(x) memset(x, 0, sizeof(x))

#define MS(x,y) memset(x, y, sizeof(x))

#define ALL(x) (x).begin(), (x).end()

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

using pi=pair<int,int>;

using repType=int;

using ll=long long;

using ld=long double;

using ull=unsigned long long;

int n,m;

const int MAXN=100005;

struct Edge

{

    int u,v,w;

    Edge() {}

    Edge(int _u, int _v, int _w):

        u(_u), v(_v), w(_w) {}

};

vector<Edge> edges;

vector<int> G[MAXN];

void add_edge(int u,int v,int w)

{

    edges.PB(u,v,w);

    G[u].PB(edges.size()-1);

}

int pa[MAXN];

int find_pa(int x)

{

    return pa[x]==x?x:pa[x]=find_pa(pa[x]);

}

bool union_pa(int x,int y)

{

    int fx=find_pa(x),

        fy=find_pa(y);

    if(fx!=fy) pa[fx]=fy;

    else return false;

    return true;

}

bool vis[MAXN];

int diameter, dp[MAXN][5];

void dfs(int now, int par)

{

    vis[now]=true;

    rep(i,0,int(G[now].size())-1)

    {

        Edge& e=edges[G[now][i]];

        int nxt=e.v;

        if(vis[nxt]) continue;

        dfs(nxt,now);

        if(dp[now][0]<dp[nxt][0]+e.w)

        {

            dp[now][1]=dp[now][0];

            dp[now][0]=dp[nxt][0]+e.w;

        }

        else if(dp[now][1]<dp[nxt][0]+e.w)

            dp[now][1]=dp[nxt][0]+e.w;

    }

    if(diameter<dp[now][0]+dp[now][1]) diameter=dp[now][0]+dp[now][1];

}

int

main()

{

    while(scanf("%d%d", &n, &m)==2)

    {

        edges.clear(); rep(i,1,n) G[i].clear();

        iota(pa+1,pa+n+1,1);

        bool has_loop=false;

        rep(i,1,m)

        {

            int u,v,w;

            scanf("%d%d%d", &u, &v, &w);

            if(has_loop) continue;

            add_edge(u,v,w);

            add_edge(v,u,w);

            if(find_pa(u)!=find_pa(v))

            {

                union_pa(u,v);

            }

            else has_loop=true;

        }

        if(has_loop) printf("YES\n");

        else

        {

            ZERO(vis);

            ZERO(dp);

            int ans=0;

            rep(i,1,n) if(!vis[i])

            {

                diameter=0;

                dfs(i,0);

                ans=max(diameter,ans);

            }

            printf("%d\n", ans);

        }

    }

    return 0;

}