HDU - 4514 湫湫系列故事——设计风景线（并查集判环）

题目：

随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。 
现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？ 
其中，可以兴建的路线均是双向的，他们之间的长度均大于0。

思路：

将给出的边的两个端点用并查集放在一起，如果这两个点的祖先相等说明构成了一个环。

在这个用并查集连成的连通分量里边，找到他的root（fa[i] = i），然后先用一个BFS找到他的端点，然后从这个端点开始找树上的最长距离。

代码：

#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#define MAX 1000000000

#define inf 0x3f3f3f3f

#define FRE() freopen("in.txt","r",stdin)

using namespace std;

typedef unsigned long long ll;

const int maxn = ;

int n,m;

struct Edge

{

    int to,w;

};

vector<Edge> mp[maxn];

int fa[maxn],vis[maxn],d[maxn];

int _find(int x)

{

    return fa[x] == x ? x : fa[x] = _find(fa[x]);

}

bool judgeLoop(int u,int v)

{

    int x = _find(u);

    int y = _find(v);

    if(x!=y)

    {

        fa[x] = y;

        return false;

    }

    return true;//x==y说明两者已经在一个连通分量里边了，也就是有环了

}

int BFS(int s)//两个作用1.查找最远的结点2.计算最长的距离

{

    memset(vis,,sizeof(vis));

    memset(d,,sizeof(d));

    vis[s] = ;

    queue<int> que;

    que.push(s);

    int ed = s,mmax=;

    while(!que.empty())

    {

        int u = que.front();

        que.pop();

        for(int i=; i<mp[u].size(); i++)

        {

            Edge e = mp[u][i];

            if(vis[e.to] == )

            {

                d[e.to] = d[u]+e.w;//获取从根节点到e.to结点的距离

                vis[e.to] = ;

                que.push(e.to);

                if(d[e.to]>mmax)//找到这棵树的距离根节点最远的结点

                {

                    ed = e.to;

                    mmax = d[e.to];

                }

            }

        }

    }

    return ed;

}

int main()

{

    //FRE();

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

    {

        for(int i=; i<maxn; i++) { fa[i] = i; mp[i].clear();}

        bool ok = false;

        for(int i=; i<m; i++)

        {

            int u,v,w;

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

            mp[u].push_back(Edge{v,w});

            mp[v].push_back(Edge{u,w});

            if(judgeLoop(u,v)) { ok = true; }

        }

        if(ok)

        {

            printf("YES\n");

            continue;

        }

        int ans = ;

        for(int i=; i<=n; i++)

        {

            if(fa[i]==i)//找到这个树的根节点(人为设置的)

            {

                int root = BFS(i);

                int temp = BFS(root);

                ans = max(ans,d[temp]);

            }

        }

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

    }

    return ;

}