hdu 4514 湫湫系列故事——设计风景线 (无向图并查集判环+非联通图的最长路径)
题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。
思路：无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。
但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。
也就是要在一个不联通的图中求最长路径。。。
没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。
不过感觉最容易想到的还是求多次直径的做法。。。
也就是。。每一个联通块求一次直径。。。取最大。。。
具体做的时候。。。加一个bool数组在bfs标记一下就好。。。
以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注意d数组初始化的问题。。。不能初始化成0x3f...（这么说来即使联通也没必要初始化成0x3f。。。。)
还有一点，这道题数据量比较大。。。用vector存图会MLE ...
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月12日 星期二 14时31分09秒
4File Name :code/hdu/4514.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32const int M=1E6+7;
33int n,m;
34int f[N];
35int lst;
36int far;
37int cnt;
38bool cyc;
39struct Edge
40{
41 int v,w;
42 int nxt;
43}edge[M];
44int d[N];
45bool vis[N];
46bool used[N];
47int head[N];
48int root ( int x)
49{
50 if (x!=f[x]) f[x] = root (f[x]);
51 return f[x];
52}
53void merge( int x,int y)
54{
55 int rx = root(x);
56 int ry = root(y);
57 if (rx==ry) return ;
58 f[rx] = ry;
59}
60void init()
61{
62 for ( int i = 1 ; i <= n ; i++) f[i] = i;
63 ms(used,false);
64 ms(head,-1);
65}
66void bfs( int s)
67{
68 ms(d,0); //初始化不能为正无穷。。。。因为本身就可能不联通。。取最大一定会得到正无穷。。。gg
69 ms(vis,false);
70 queue<int>q;
71 q.push(s);
72 vis[s] = true;
73 while (!q.empty())
74 {
75 int u = q.front();q.pop();
76 used[u] = true;
77 for ( int i = head[u] ; i != -1; i=edge[i].nxt)
78 {
79 int v = edge[i].v;
80 int w = edge[i].w;
81 if (vis[v]) continue;
82 vis[v] = true;
83 d[v] = d[u] + w;
84 q.push(v);
85 }
86 }
87}
88void addedge(int u,int v,int w)
89{
90 edge[cnt].v = v;
91 edge[cnt].w = w;
92 edge[cnt].nxt = head[u];
93 head[u] = cnt;
94 cnt++;
95}
96int treeDiameter( int s)
97{
98 bfs(s);
99 int mx = 0 ;
100 lst = s;
101 for ( int i = 1 ; i <= n ; i++)
102 {
103 if (d[i]>mx)
104 {
105 mx = d[i];
106 lst = i;
107 }
108 }
109 far = 0 ;
110 bfs(lst);
111 for ( int i = 1 ; i <= n ; i++)
112 {
113 if (d[i]>far)
114 {
115 far = d[i];
116 }
117 }
118 return far;
119}
120int main()
121{
122 #ifndef ONLINE_JUDGE
123 freopen("code/in.txt","r",stdin);
124 #endif
125 while (~scanf("%d%d",&n,&m))
126 {
127 init();
128 cnt = 0 ;
129 cyc = false;
130 for ( int i = 1; i <= m ; i++)
131 {
132 int u,v,w;
133 scanf("%d%d%d",&u,&v,&w);
134 addedge(u,v,w);
135 addedge(v,u,w);
136 if (root(u)==root(v))
137 {
138 cyc = true;
139 continue;
140 }
141 merge(u,v);
142 }
143 if (cyc)
144 {
145 puts("YES");
146 continue;
147 }
148 int ans = 0 ;
149 for ( int i = 1 ; i <= n ; i++)
150 {
151 if (!used[i]) ans = max(ans,treeDiameter(i));
152 }
153 cout<<ans<<endl;
154 }
155 #ifndef ONLINE_JUDGE
156 fclose(stdin);
157 #endif
158 return 0;
159}