HDOJ4514 并查集判环+BFS求最长路

湫湫系列故事——设计风景线

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 5286 Accepted Submission(s): 973

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

Source
2013腾讯编程马拉松初赛第二场（3月22日）

Recommend
liuyiding | We have carefully selected several similar problems for you: 6193 6192 6191 6190 6189

判断是否成环用并查集，若两个点的父亲一样那么环存在。
最长路简单的宽搜就可以了。
注意开的数组规模。。开小了就一直没AC。。

#include <iostream>
#include <cstring>
#include <ctime>
#include <cmath>
#include <queue>
using namespace std;

const int maxn = 1e5+5;
const int maxm = 2e6+5;
int head[maxn],f[maxn],dis[maxn];
bool vis[maxn],used[maxn],flag;
int i,j,k,tot,max_len,m,n;
struct node{
   int to,next,len;
}edge[maxm];
queue<int>que;

void add_edge(int u, int v, int w){
     edge[tot].next = head[u];
     edge[tot].to = v;
     head[u] = tot;
     edge[tot].len = w;
     tot++;
}

int Find(int x){
   if (f[x]==x) return x;
   return f[x] = Find(f[x]);
}

void Merge(int x, int y){
    int fx = Find(x), fy = Find(y);
    f[fx] = fy;
}

void init(){
     int u,v,w;
     tot = 0;
     flag = 0;
     max_len = 0;
     for (i=0; i<=n; i++) {f[i] = i;  head[i] = -1; used[i] = 0;}
     for (i=0; i<m; i++) {
         cin >> u >> v >> w;
         add_edge(u,v,w);
         add_edge(v,u,w);
         if (Find(u)!=Find(v)) Merge(u,v);
         else flag = 1;
     }
}

void bfs(int s){
     memset(vis,0,sizeof(vis));
     memset(dis,0,sizeof(dis));
     while(!que.empty()) que.pop();
     que.push(s);
     vis[s] = 1;
     int u,v;
     while (!que.empty()) {
        u = que.front();
        used[u] = 1;
        que.pop();
        for (int i=head[u]; i!=-1; i=edge[i].next){
            v = edge[i].to;
            if (!vis[v]) {
                dis[v] = dis[u]+edge[i].len;
                vis[v] = 1;
                que.push(v);
            }
        }
     }
}

void work(int s){
   int pos = s,maxl = 0;
   bfs(s);
   for (int k=1; k<=n; k++) if (dis[k]>maxl) {
       maxl = dis[k];
       pos = k;
   }
   bfs(pos);
   for (int k=1; k<=n; k++) max_len = max(max_len,dis[k]);
}

int main(){
    std::ios::sync_with_stdio(false);
    while (cin >> n >> m) {
        init();
        if (flag) cout << "YES" << endl;
        else {
            for (i=1; i<=n; i++) if (!used[i]) work(i);
            cout << max_len << endl;
        }
    }
    return 0;
}