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

Posted on | In ,

思路

并查集判环+树的直径。注意树有可能是不连通的。
树的直径通过两次bfs就能得到，具体证明见树的直径（最长路）的详细证明

代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

const int MAXN=100005;
const int MAXM=2000005;
int n,m;
int fa[MAXN],ranks[MAXN];
int head[MAXN],to[MAXM],nexts[MAXM],wei[MAXM],edge,dis[MAXN];
bool vis[MAXN],used[MAXN];
queue<int> Q;
void init(int n){
    edge=0;
    ms(head,-1),ms(vis,0);
    for(int i=0;i<=n;i++)fa[i]=i,ranks[i]=0;;
}
int getfa(int x){
    if(fa[x]==x)return x;
    else return fa[x]=getfa(fa[x]);
}
void unite(int x,int y){
    x=getfa(x),y=getfa(y);
    if(x==y)return;
    if(ranks[x]<ranks[y])fa[x]=y;
    else{
        fa[y]=x;
        if(ranks[x]==ranks[y])ranks[x]++;
    }
}
bool same(int x,int y){
    return getfa(x)==getfa(y);
}
void addEdge(int u,int v,int w){
    wei[edge]=w,to[edge]=v,nexts[edge]=head[u],head[u]=edge++;
    wei[edge]=w,to[edge]=u,nexts[edge]=head[v],head[v]=edge++;
}
void bfs(int s){
    ms(used,0),ms(dis,0);
    used[s]=1,dis[s]=0;
    while(!Q.empty())Q.pop();
    Q.push(s);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        vis[u]=1;
        for(int i=head[u];~i;i=nexts[i]){
            int v=to[i];
            if(!used[v]){
                used[v]=1;
                dis[v]=dis[u]+wei[i];
                Q.push(v);
            }
        }
    }
}

int treedim(int s){
    int u=s,maxs=0;
    bfs(s);
    for(int i=1;i<=n;i++){
        if(dis[i]>maxs)u=i,maxs=dis[i];
    }
    bfs(u);
    maxs=0;
    for(int i=1;i<=n;i++)maxs=max(maxs,dis[i]);
    return maxs;
}

int main() {
	int u,v,w;
	while(~scanf("%d%d",&n,&m)){
        init(n);
        int flag=0;
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&w);
            if(same(u,v))flag=1;
            unite(u,v);
            addEdge(u,v,w);
        }
        if(flag)printf("YES\n");
        else{
            int maxs=-1;
            for(int i=1;i<=n;i++){
                if(!vis[i])maxs=max(maxs,treedim(i));
            }
            printf("%d\n",maxs);
        }
	}
	return 0;
}