OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【APIO2010】巡逻

【题目描述】

在一个地区中有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条道路后能达到的最小巡逻距离。

【输入样例】

8 2

1 2

3 1

3 4

5 3

7 5

8 5

5 6

【输出样例】

10

【数据范围】

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

30%的数据中,K=1;

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

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

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

【题解】

添加一条边后,原图会变成一棵外向树,环上的边仅用走一次,故当k=1时,我们只用求出树上最长链,在链的两端之间加一条边即可,答案为(n-1)*2-最长链长度+1。

考虑k=2的情况,第一条添加的边当然同k=1的情况,我们主要考虑第二条边。类似的,我们要找出一条“较长的链”,把链的两端连接起来,但答案不一定是次长链/另一条最长链,因为两条链的相交部分其实一点都没省下来,还是得走两遍。不过这点恰好是解决问题的关键,我们只需要把原来求出的最长链边权都设为-1,再求一遍最长链就是答案了。为什么这样是正确的?因为假如两次都选择了同一条边,其实预算的答案是减少了2,而实际上没有减少,所以设为-1,恰好抵消了前一次的预算。

注意第二次无法bfs求最长链(因为有负权),所以要设计一种奇怪的树形DP囧

【代码】

1A,再接再厉~

http://paste.ubuntu.com/11739346/

评论

© OI技术宅 | Powered by LOFTER