洛谷 P3629 [APIO2010]巡逻 题解【树的直径】【树形DP】【贪心】

作者: wjyyy 分类: ,树形DP,树的直径,解题报告,贪心 发布时间: 2018-06-28 17:53

点击量:19

 

   这个题真的只考树的直径啊。。。

 

题目描述

在一个地区中有n个村庄,编号为1, 2, …, n。有n–1条道路连接着这些村 庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为1个单位。 为保证该地区的安全,巡警车每天要到所有的道路上巡逻。警察局设在编号为1的村庄里,每天巡警车总是从警察局出发,最终又回到警察局。下图表示一个有8个村庄的地区,其中村庄用圆表示(其中村庄1用黑色的圆表示),道路是连接这些圆的线段。为了遍历所有的道路,巡警车需要走的距离为14个单位,每条道路都需要经过两次。

为了减少总的巡逻距离,该地区准备在这些村庄之间建立 K 条新的道路, 每条新道路可以连接任意两个村庄。两条新道路可以在同一个村庄会合或结束 (见下面的图例(c))。 一条新道路甚至可以是一个环,即,其两端连接到同一 个村庄。 由于资金有限,K 只能是 1 或 2。同时,为了不浪费资金,每天巡警车必须 经过新建的道路正好一次。 下图给出了一些建立新道路的例子:

在(a)中,新建了一条道路,总的距离是 11。在(b)中,新建了两条道路,总 的巡逻距离是 10。在(c)中,新建了两条道路,但由于巡警车要经过每条新道路 正好一次,总的距离变为了 15。 试编写一个程序,读取村庄间道路的信息和需要新建的道路数,计算出最佳 的新建道路的方案使得总的巡逻距离最小,并输出这个最小的巡逻距离。

输入输出格式

输入格式:

第一行包含两个整数 n, K(1≤K≤2)。接下来n–1行,每行两个整数a,b, 表示村庄 a 与 b 之间有一条道路(1 ≤ a, b ≤ n)。

输出格式:

输出一个整数,表示新建了K条道路后能达到的最小巡逻距离。

输入输出样例

输入样例#1:
8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6
 
输出样例#1:
11
 
输入样例#2:
8 2
1 2
3 1
3 4
5 3
7 5
8 5
5 6
 
输出样例#2:
10
 
输入样例#3:
5 2
1 2
2 3
3 4
4 5
 
输出样例#3:
6
 

说明

10%的数据中,n≤1000, K=1;

30%的数据中,K=1;

80%的数据中,每个村庄相邻的村庄数不超过 25;

90%的数据中,每个村庄相邻的村庄数不超过 150;

100%的数据中,3≤n≤100,000, 1≤K≤2。

 

   我们如果要把每条道路都走一遍,根据树的性质,一定是每条边走2遍(隐含条件:回到1号点)。那么我们如果新建一条边,就会成环,如果链的长度为L,那么原来链上需要走的距离是L×2,现在变成了L+1,也就是只需要L+1次就可以把这个环走完并回到环的起点,所节省的距离为\(2L-(L+1)=L-1\),随L,也就随链或环的大小单调递增。那么我们要使原来的链最长,就是树的直径。求树的直径有两种方法:两次dfs和树形DP。这道题方便起见,我两种都用到了。

 

   首先当k=1时,求出直径,用所有边的2倍减去直径的长度再减1(意味着新加的一条边),就是答案。而当k=2时,我们要对这张图稍作处理。

 

   首先根据贪心,我们需要做上一步的操作。对于下一步,我们要继续找树的直径。但是此时已经有一条链是被选入环里了,我的第一想法是把环缩掉,因为环不能对答案有贡献了,把环缩成一个点,这样就能找到新的直径,重复一开始的过程。但是这样是错的,因为环虽然不能对答案有正的贡献,但是会有负的。我们如果不管原来的环,只管没有缩掉的枝节,就会出现这种情况:

   如上是一个树的一部分,黄色部分是已经找出来的环。那么我们把它缩点成右边图的形式,缩点前后实际上是有区别的。

   左边原图的实际路程是3,而右侧只有2。而当k=1时,左边这条路径是5步,右边路径是4步。我们如果把这一段当成环,在右边的贡献是1(4-2[双向变单向]+1[新建的边]=3)。但看左边的图,中间一部分就重复走过了,贡献只有0(5-2[双向变单向]+1[单向变双向]+1[新建的边]=5)因此这种做法是错的。

 

   通过研究这种错误的做法,发现环不能缩,而环上边的贡献是-1,我们就可以把原来直径上的边权(注意双向)改成-1,把这点负贡献归为直径长度的贡献,再做一遍第一步就可以了。

 

   不过此时树上有负权边,两次DFS是个贪心(像dijkstra),不能处理负权边,我们要用树形DP求解;简单介绍一下树形DP方法:

对于每个点,找出最长链,最长链最多包含2个孩子,所以我们要存已经找到的孩子的状态去更新正在找的孩子的状态。也就是把当前状态先更新,再拿去更新其他状态(有点像容量为2的01背包?)具体可以看代码片段:

Dfs(p->n);
mx=mx>f[x]+f[p->n]+p->v?mx:f[x]+f[p->n]+p->v;//先更新答案
f[x]=f[x]>f[p->n]+p->v?f[x]:f[p->n]+p->v;//再更新当前最优链

 

   对于第一次找树的直径,并更新树的直径上的边权,用两次dfs做是最好的,因为没有负权,并且容易存储路径,也简单好写。

Code:

#include<cstdio>
struct node
{
    int n,v;
    node *nxt,*op;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
        op=NULL;
    }
    node()
    {
        nxt=NULL;
        op=NULL;
    }
};
node head[100100],*tail[100100];
int d1,d2,L=0,l,flag=0;
int Pre[100100];
node *pre[100100];
void dfs(int x)
{
    if(l>L)
    {
        L=l;
        if(flag==0)
            d1=x;
        else
            d2=x;
    }
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(p->n==Pre[x])
            continue;
        Pre[p->n]=x;
        pre[p->n]=p;
        l+=p->v;
        dfs(p->n);
        l-=p->v;
    }
}
int f[100100];
int mx=0;
void Dfs(int x)
{
    node *p=&head[x];
    f[x]=0;
    int son=0;
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(p->n==Pre[x])
            continue;
        Pre[p->n]=x;
        Dfs(p->n);
        mx=mx>f[x]+f[p->n]+p->v?mx:f[x]+f[p->n]+p->v;
        f[x]=f[x]>f[p->n]+p->v?f[x]:f[p->n]+p->v;
    }
}
int main()
{
    int n,k,u,v;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        tail[i]=&head[i];
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        tail[u]->nxt=new node(v,1);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u,1);
        tail[v]=tail[v]->nxt;
        tail[u]->op=tail[v];//双向边都要修改
        tail[v]->op=tail[u];
    }
    l=0;
    Pre[1]=1;//求路径用的
    dfs(1);//求直径的一个端点
    flag=1;
    L--;
    l=0;
    Pre[d1]=d1;
    dfs(d1);//求完整直径
    flag=0;
    int t=d2;
    while(t!=d1)
    {
        pre[t]->v=-1;
        pre[t]->op->v=-1;
        t=Pre[t];
    }
    int ans=2*(n-1)-(L-1);//现在所要走的路程
    if(k==1)
    {
        printf("%d\n",ans);
        return 0;
    }
    Pre[1]=1;
    Dfs(1);//找新的直径
    ans-=mx-1;
    printf("%d\n",ans);
    return 0;
}

 

 

2
说点什么

avatar
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
wjyyyRye_Catcher Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Rye_Catcher
游客

Orz感谢博主

/* */