问题描述:

在一个地区中有n(3≤n≤100000)个村庄,编号为 1, 2, …, n。有 n – 1 条道路连接着这些村 庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为 1 个单位。 为保证该地区的安全,巡警车每天要到所有的道路上巡逻。警察局设在编号 为 1 的村庄里,每天巡警车总是从警察局出发,最终又回到警察局。

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

试编写一个程序,读取村庄间道路的信息和需要新建的道路数,计算出最佳 的新建道路的方案使得总的巡逻距离最小,并输出这个最小的巡逻距离。

输入:

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

输出:

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

思路:

我们先考虑k=1的情况,这应该不难想到就是求树的直径(最长链),然后答案就是$(n-1)*2-len+1$($len$为直径)。

然后考虑k=2的情况,也可以用同样的思路,找树的直径。同样先找出第一个最长链然后更新答案,但第二次找最长链时要考虑第一个最长链造成的影响。这时我们可以想到将第一条直径上边权取反然后再找第二条边就OK了,然后再用长度更新答案$ans=ans-len+1$。

我们考虑如何找直径,一般有两种放方法,第一种是树形DP,还有一种是两边bfs。这个地方要注意最长链取反之后会出现负边权,用bfs的方法会出现BUG,只能用树形DP的方法。

我码完了BFS的代码后跑样例才发现了这个BUG,先弄清思路再开始码真的很重要!!!

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 100005
using namespace std;

int n, k, root, cnt=1, ans, temp, vis[MAXN], dis[MAXN], head[MAXN], son1[MAXN*2], son2[MAXN*2];

struct Edge {int next, to, dis;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=1;
    head[from]=cnt;
}

int dfs(int x, int fa)
{
    int len1=0, len2=0;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        int len=dfs(to, x)+edge[i].dis;
        if(len>len1)
        {
            len2=len1; len1=len;
            son2[x]=son1[x]; son1[x]=i;
        }
        else if(len>len2) len2=len, son2[x]=i;
    }
    if(len1+len2>temp) temp=len1+len2, root=x;
    return len1;
}

int main()
{
    scanf("%d%d", &n, &k);
    ans=n*2-2;
    for(int i=1; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs(1, 0);
    ans-=temp-1;
    if(k==2)
    {
        temp=0;
        for(int i=son1[root]; i; i=son1[edge[i].to]) edge[i].dis=edge[i^1].dis=-1;
        for(int i=son2[root]; i; i=son1[edge[i].to]) edge[i].dis=edge[i^1].dis=-1;
        dfs(1, 0);
        ans-=temp-1;
    }
    printf("%d\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注