[APIO2010]巡逻 题解

作者:神秘网友 发布时间:2021-02-15 20:50:17

[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 条道路后能达到的最小巡逻距离。

输入输出样例

输入 #1
8 1 
1 2 
3 1 
3 4 
5 3 
7 5 
8 5 
5 6 
输出 #1
11

发现原题木有\(\KaTeX\)啊,那么我也不改了吧。

题目解析

我们分两种情况讨论:\(k=1\)和\(k=2\)
当新增加一条边的时候,就会组成一个环,假设这条道路连接的两个点距离是\(l\),这样就可以减少\(l-1\)的距离,长度就是\(2\times\left( n-1\right)-\left( l-1 \right)=2n-l-1\)
显然要使\(l\)最大,其实就是这棵树的直径。
当\(k=2\)的时候,就需要在\(k=1\)的情况下再加一条边就可以了。假设这条道路连接的两个点距离是\(l_2\)。如果这两个环不重合,那么最后的距离就是\(2\times \left( n-1 \right)-\left(l-1\right)-\left(l_2-1\right)=2n-l-l_2\)。如果这两个环重合了,由于新建的道路必须经过\(1\)次,所以最后的距离还是\(2n-l-l_2\)。
要使答案最大,就要用\(l+l_2\)最大了,当\(l\)为树的直径时,即树内的最长链,\(l_2\)就是树上第二长的链。
但是,我们怎么求树的第二长链呢
我们先求出树的直径,然后求出直径路径,具体做法详见blog。然后把树的直径上的边权改成\(-1\)(或者是一个负数),再跑一次树的直径就可以了。(当然这是一棵带边权的树,初始边权为\(1\))。
代码如下:

#includecstdio
#includecstring
#define max(a,b) ((a)(b)(a):(b))
#define maxn 2000039
using namespace std;
int head[maxn],to[maxn],nex[maxn],v[maxn],k;
#define add(x,y,z); nex[++k]=head[x];\
to[k]=y;\
head[x]=k;\
v[k]=z;
int n,m,x,y,z;
int maxx;
int f[maxn],g[maxn][3],node;
void dfs(int num,int pre){  
	f[num]=0;
	for(int i=head[num];i!=-1;i=nex[i])
        if(to[i]!=pre){
            dfs(to[i],num);
            maxx=max(maxx,f[num]+f[to[i]]+v[i]);
            f[num]=max(f[to[i]]+v[i],f[num]);
        }
    return;
}
void dfss(int num,int pre){  
	f[num]=0;
	int max1,max2;
	max1=max2=0;
	for(int i=head[num];i!=-1;i=nex[i])
        if(to[i]!=pre){
            dfss(to[i],num);
            if(f[to[i]]+v[i]max1){
            	max2=max1; g[num][2]=g[num][1];
            	max1=f[to[i]]+v[i];
            	g[num][1]=to[i];
			}
			else if(f[to[i]]+v[i]max2){
				max2=f[to[i]]+v[i];
            	g[num][2]=to[i];
			}
            f[num]=max(f[to[i]]+v[i],f[num]);
        }
    if(max1+max2maxx){
    	maxx=max1+max2;
    	node=num;
	}
    return;
}
void del(int x,int y){
	for(int i=head[x];i!=-1;i=nex[i]){
		if(to[i]==g[x][y]){
			v[i]=-1;
			del(to[i],1);
		}
	}
	return;
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",n,m);
    for(int i=1;in;i++){
        scanf("%d%d",x,y);
		add(x,y,1);
        add(y,x,1);
    }
    if(m==1){
    	maxx=-10000000000;
    	dfs(1,0);
    	printf("%d",(n-1)*2-(maxx-1));
	}
	else{
		maxx=0;
		dfss(1,0);
		int maxy=maxx;
		maxx=0;
		del(node,1);
		del(node,2);
		dfs(1,0);
		printf("%d",n*2-maxx-maxy);
	}
    return 0;
}

[APIO2010]巡逻 题解 相关文章

  1. USACO16DEC LuoguP3405 Cities and States S 题解

    题目传送门 题目描述 To keep his cows intellectually stimulated, Farmer John has placed a large map of the USA on the wall of his barn. Since the cows spend many hours in the barn staring at this map, they start to notice several curious pa

  2. POJ3784 Running Median 题解

    题目描述 For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far. 输入 The first line of input co

  3. CF1400A String Similarity 题解

    题目传送门 题目解析 第一眼思路:暴搜。然而会T飞,所以不考虑。 我们模拟一下得到答案的过程:(这里以样例第二个点为例) 1110 11000 0000 我们发现在 \(1110000\) 这一串中,最中间的一个数字 \(0\) 在每一个数字中都出现过,并且在不同的位置出现,所以

  4. CF 1400C Binary String Reconstruction 题解

    题目传送门 题目解析 总感觉这道题目和CF468B的思路很像。 我们发现,如果数组 \(s_i=0\) 那么 \(w_{i-x}=w_{i+x}=0\) 。但是如果 \(s_i=1\) 那么我们就不可以确定 \(w_{i-x}\) 和 \(w_{i+x}\) 的值。 所以我们先进行一次处理:首先,令所有的 \(w_i=1\) 。

  5. CF1393B Applejack and Storages 题解

    目录 题目翻译 题目解析 代码 题目传送门 题目翻译 你需要维护一个序列,让它满足一下操作: 插入一个数字 删除一个数字,保证这个数字是存在 在每次删除和插入之后查询这些数字是否可以组成一个正方形和矩形 题目解析 为了方便,我们可以开一个桶,这样就变

  6. CCC 2015 state1-s5 Greedy For Pies 糖果派 题解

    目录 题目 题目翻译 题目解析 DP式 细节 代码 题目 Problem Description The local pie shop is offering a promotion - all-you-can-eat pies! Obviously, you can’t pass up this offer. The shop lines up \(N\) pies from left to right - the ith pie c

  7. [NOI 2001] 陨石的秘密 题解

    题目传送门 思路 首先我们发现可以搜索,但是明显会TLE,因为组合数学的结果是以指数倍增长的,结果会很大,明显不行。 由于不要输出路径,那么考虑DP。 令\(f_{i,j,k,d}\)为深度\(d\), {} \(i\)对, [] \(j\)对, () \(k\)对的结果。 我们发现这样很难得出

  8. [NOIP2014] 解方程 题解

    题目传送门 题目描述 已知多项式方程: \[a0+a1*x+a2*x^2+\dots+an*x^n=0\] 求这个方程在 \([1,m]\) 内的整数解(\(n\) 和 \(m\) 均为正整数)。 输入格式 输入共 \(n + 2\) 行。 第一行包含 \(2\) 个整数 \(n, m\),每两个整数之间用一个空格隔开。 接下来

  9. CCC2014 S5 Lazy Fox 题解

    题目传送门 Problem Description You have a pet Fox who loves treats. You have N neighbours at distinct locations (described as points on the Cartesian plane) which hand out treats to your pet Fox, and each neighbour has an unlimited number

  10. 题解 洛谷P2482 【[SDOI2010]猪国杀】

    概述 题号 难度 \(AC\)时间及记录 \(\texttt{洛谷P2482}\) \(\texttt{洛谷难度:省选/NOI-}\) \(\texttt{On 2021/02/15}\) 解析 导语部分 这是一道 传说 级别的题目。 最近状态不好,只好逼自己刷一道大型 模拟 题。 那么言归正传,我们先得梳理一下题目大意

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词