首页 > itarticle > 洛谷p1099树网的核题解

洛谷p1099树网的核题解

admin 11月 27, 2020 0


楼上各种巨神的算法大致领略了，这里提供一个超暴力的写法（因为发现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
 

#define N 3000
using namespace std;
inline int ()
{
   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;
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能