HDU 4514 - 湫湫系列故事——设计风景线 - [并查集判无向图环][树形DP求树的直径]

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4514

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Problem Description

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

 

Input

　　测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；
　　接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。

　　[Technical Specification]
　　1. n<=100000 
　　2. m <= 1000000
　　3. 1<= u, v <= n 
　　4. w <= 1000

 

Output

　　对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。

 

Sample Input

3 3

1 2 1

2 3 1

3 1 1

 

Sample Output

YES

题解：

并查集判无向图环，这个算是很简单的并查集模板应用了；

只是需要注意，如果出现环，就停止往邻接表中添加边，否则会MLE；

树形DP求树的直径，这个也是模板应用，

唯一需要注意的是，有可能连通分量不止一个。

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=+;

int n,m;

struct Edge{

    int u,v,w;

    Edge(int u,int v,int w){this->u=u,this->v=v,this->w=w;}

};

vector<Edge> E; int E_size;

vector<int> G[maxn];

void adjListInit(int l,int r)

{

    E.clear(); E_size=;

    for(int i=l;i<=r;i++) G[i].clear();

}

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

{

    E.push_back(Edge(u,v,w)); E_size++;

    E.push_back(Edge(u,v,w)); E_size++;

    G[u].push_back(E_size-);

    G[v].push_back(E_size-);

}

int par[maxn];

void UFSinit(int l,int r){for(int i=l;i<=r;i++) par[i]=i;}

int find(int x){return (par[x]==x)?x:(par[x]=find(par[x]));}

void unite(int x,int y)

{

    x=find(x),y=find(y);

    if(x==y) return;

    par[y]=x;

}

inline bool isSame(int x,int y){return find(x)==find(y);}

int diameter,dp[maxn][];

bool vis[maxn];

void dfs(int now,int par)

{

    vis[now]=;

    for(int i=;i<G[now].size();i++)

    {

        Edge &e=E[G[now][i]]; int nxt=e.v;

        if(vis[nxt]) continue;

        dfs(nxt,now);

        if(dp[now][] < dp[nxt][]+e.w) // ( "其某个孩子的最大"+"其与孩子的距离" ) > "最大" > "次大"

        {

            dp[now][] = dp[now][];

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

        }

        else if(dp[now][] < dp[nxt][]+e.w) // "最大" > ( "其某个孩子的最大"+"其与孩子的距离" ) > "次大"

        {

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

        }

    }

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

}

int ans;

int main()

{

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

    {

        bool haveRing=;

        adjListInit(,n);

        UFSinit(,n);

        for(int i=,u,v,w;i<=m;i++)

        {

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

            if(haveRing) continue;

            addEdge(u,v,w);

            if(!isSame(u,v)) unite(u,v);

            else haveRing=;

        }

        if(haveRing)

        {

            printf("YES\n");

            continue;

        }

        memset(vis,,sizeof(vis));

        memset(dp,,sizeof(dp));

        ans=;

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

        {

            if(vis[i]) continue;

            diameter=;

            dfs(i,);

            ans=max(diameter,ans);

        }

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

    }

}