湫湫系列故事——设计风景线
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; }