洛谷P1099树网的核题解

楼上各种巨神的算法大致领略了,这里提供一个超暴力的写法(因为发现NOIP当年这道题的数据很水,然而bzoj1999的数据就水不过了…)

只是想记录一下自己的暴力程序……

总之,要找核,先是要找树的直径(最长链),找树的直径只需要先从一个点(随便是什么)遍历,找到距离它最远的一个点,那么这个点肯定就是树的直径的一端了,从找到的这一端再遍历一次,找到距离这个端点最远的点,这个点就是另外一端了,这个应该都会搞

在遍历第二次的时候就将树改成了以直径一个端点为根的有根树,这样直径上每个点就可以通过父亲节点的记录来枚举路径

1
2
3
4
5
6
7
for(int i=r;i;i=fa[i])//开始枚举
{
for(int j=i;j;j=fa[j])
{
......
}
}

就是这么暴力……

枚举的过程中求最小偏心距

代码如下

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#define N 3000
using namespace std;
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node
{
int u;
int v;
int w;
int next;
}q[N];
int n,s,num=0,head[N],inq[N],fa[N],father[N],dist[N],dis[N],ans=2147483647,ans2=(-2147483647);
void add(int x,int y,int z)
{
q[num].u=x;q[num].v=y;q[num].w=z;q[num].next=head[x];head[x]=num++;
}
void dfs(int x)
{
for(int i=head[x];i!=-1;i=q[i].next)
{
int to=q[i].v;
if(!inq[to]&&to!=fa[x])
{
fa[to]=x;
dist[to]=dist[x]+q[i].w;
dfs(to);
}
}
}
void dfs2(int x)
{
for(int i=head[x];i!=-1;i=q[i].next)
{
int to=q[i].v;
if(!inq[to]&&to!=father[x])
{
father[to]=x;
dis[to]=dis[x]+q[i].w;
dfs2(to);
}
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(dist,0,sizeof(dist));
memset(fa,0,sizeof(fa));
n=read(),s=read();
for(int i=1;i<=n-1;i++)
{
int x,y,z;
x=read(),y=read(),z=read();
add(x,y,z);
add(y,x,z);
}
dist[1]=0;
dfs(1);//以1为起点先搜一遍,因为距1最远的一个点肯定是最长链的一个端点,不然就不是最长链了
int l=1,r=0;
for(int i=1;i<=n;i++)
{
if(dist[i]>dist[l])l=i;
}
memset(fa,0,sizeof(fa));
dist[l]=0;
dfs(l);//然后以找到的端点搜一遍,距离他最远的肯定就是最长链另一端了!
for(int i=1;i<=n;i++)
{
if(dist[i]>dist[r])r=i;
}
for(int i=r;i;i=fa[i])//开始枚举
{
for(int j=i;j;j=fa[j])
{
if(dist[i]-dist[j]<=s)
{
memset(inq,0,sizeof(inq));
ans2=(-2147483647);
for(int k=i;k!=j;k=fa[k])
{
inq[k]=1;
}
inq[j]=1;//记录哪些点在路径之中
for(int k=i;k!=j;k=fa[k])
{
memset(father,0,sizeof(father));
dis[k]=0;
dfs2(k);//路径上每个点向其他不在路径,也就是不在直径中的点去遍历
}
memset(father,0,sizeof(father));
dis[j]=0;
dfs2(j);
for(int i=1;i<=n;i++)
{
ans2=max(ans2,dis[i]);
}
ans=min(ans2,ans);//最小偏心距
}
else break;
}
}
printf("%d",ans);
return 0;
}