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

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp 并查集

给一个无向图,问是否存在环,存在就YES,如果不存在,输出一条最长路径的长度

判断有没有环(因为环也没要求包括所有点),用一个并查集就行了

如果无环,那么这个无向图必然是一个无根树(森林),就在树上进行一次树DP求最长路即可,简单题

可以不开栈挂

但是注意,这题边数很大,居然会爆空间

本来是存u,v,w,next的,虽然u可要可不要,但我习惯一般是存的

这题爆空间,去掉u,居然就不爆了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define M 1000010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int dp[N][2],ans;
int p[N];
int n,tot,head[N];
struct edge{
int v,w,next;
}e[2*M];
bool vis[N];

void add(int u,int v,int w){
e[tot].v = v; e[tot].w = w;
e[tot].next = head[u]; head[u] = tot++;
}

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

void dfs(int u){
vis[u] = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v , w = e[k].w;
if(vis[v]) continue;
dfs(v);
if(dp[v][0] + w > dp[u][0]){
dp[u][1] = dp[u][0];
dp[u][0] = dp[v][0] + w;
}
else if(dp[v][0] + w > dp[u][1]){
dp[u][1] = dp[v][0] + w;
}
}
ans = max(ans,dp[u][0]+dp[u][1]);
}

int main(){
//freopen("grated.txt","w",stdout);
int m;
while(scanf("%d%d",&n,&m)!=EOF){
tot = 0; cl(head,-1);
for(int i = 1; i <= n; i++)
p[i] = i;
bool res = false;
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
int fau = find(u);
int fav = find(v);
if(fau == fav) res = true;
p[fav] = fau;
}
if(res){
puts("YES"); continue;
}
ans = -1; cl(vis,false); cl(dp,0);
for(int i = 1; i <= n; i++)
if(!vis[i])
dfs(i);
printf("%d\n",ans);
}
return 0;
}