文章关键词:bzoj1912 Apio2010 patrol 巡逻 De

[bzoj1912][Apio2010]patrol 巡逻

作者:神秘网友 发布时间:2021-11-25 14:06:45

[bzoj1912][Apio2010]patrol 巡逻

Description

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

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

Sample Input

8 1 
1 2 
3 1 
3 4 
5 3 
7 5 
8 5 
5 6

Sample Output

11

HINT
3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

Solution
不建道路时方案数为2(n-1)。
建一条道路时,把树直径两段连上,答案为2(n-1)-r+1。
此基础上再建一条道路:把树直径删去,在现在的图上再求一条直径。

那么,\(k\leq10^5\)要怎么做呢

#define N 100005
struct graph{
	int nxt,to,w;
}e[N1];
int g[N],f1[N],f2[N],n,m,mx,id,ans,cnt=1;
bool vis[N];
inline void addedge(int x,int y){
	e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;e[cnt].w=1;
}
inline void adde(int x,int y){
	addedge(x,y);addedge(y,x);
}
inline int dfs(int u,int fa){
	int s1=0,s2=0;
	for(int i=g[u],tmp;i;i=e[i].nxt)
		if(e[i].to!=fa){
			tmp=e[i].w+dfs(e[i].to,u);
			if(tmps1){
				s2=s1;s1=tmp;f2[u]=f1[u];f1[u]=i;
			}
			else if(tmps2){
				s2=tmp;f2[u]=i;
			}
		}
	if(s1+s2mx) mx=s1+s2,id=u;
	return s1;
}
inline void Aireen(){
	n=read();m=read();
	for(int i=1;in;++i)
		adde(read(),read());
	ans=(n-1)1;
	while(m--){
		memset(f1,0,sizeof(f1));
		memset(f2,0,sizeof(f2));
		mx=id=0;dfs(1,0);ans+=1-mx;
		for(int i=f1[id];i;i=f1[e[i].to]) e[i].w=e[i^1].w=-1;
		for(int i=f2[id];i;i=f1[e[i].to]) e[i].w=e[i^1].w=-1;
	}
	printf("%d\n",ans);
}

2017-05-03 22:23:28


本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

[bzoj1912][Apio2010]patrol 巡逻 相关文章

  1. [APIO2010]巡逻 题解

    你谷题目传送门 题目描述 在一个地区中有 n 个村庄,编号为 1, 2, ..., n。有 n 1 条道路连接着这些村 庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为 1 个单...

  2. P3628 [APIO2010]特别行动队

    P3628 [APIO2010]特别行动队 题目描述 你有一支由 n 名预备役士兵组成的部队,士兵从 1 到 n 编号,要将他们拆分 成若干特别行动队调入战

  3. bzoj1834: [ZJOI2010]network 网络扩容

    bzoj1834: [ZJOI2010]network 网络扩容 Time Limit:3 SecMemory Limit:64 MB Submit:3147Solved:1624 [Submit][Status][Discuss] 给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求: 1、 在不扩容的情况下,1

  4. 【BZOJ1818】【CQOI2010】【XSY2428】内部白点(树状数组+扫描线

    【BZOJ1818】【CQOI2010】【XSY2428】内部白点(树状数组+扫描线) 先把所有点的 x x x坐标离散化。 然后分别将所有点按 x x x、 y y y排序。这里以按 x x x排序为例,对于 x x x坐标相同的两个点,我们把它们连成一条线段。那么按 y y y...

  5. 研究报告分享2020年3月研究报告行业报告论文报告1912份

    【研究报告分享】2020年3月研究报告行业报告论文报告,1912份 2020年3月研究报告资料包,目前搜集1912分,包含重点报告、公司研究、行业研究、疫情相关研究报告、宏观经济。(3月份已更新完,获取方式在文章底部) 重点精选...

  6. 杭州城市大脑发布AI视觉产品“天曜”,用机器巡逻替代人巡逻

    杭州城市大脑发布AI视觉产品“天曜”,用机器巡逻替代人巡逻 4月8日,杭州城市大脑发布AI产品“天曜”,升级监控球机智能感知系统,通过自动跟踪识别与智能感知技术,使其具备城市级大规模摄像头的实时分析能力,在监...

  7. 巡逻防控工作方案

    范文大全-www.tqwba.com 工作方案是对未来要做的重要工作做了最佳安排,并具有较强的方向性、导性粗线条的筹划,是应用写作的计划性文体之一,在现代领导科学中,为达到某一特定效果,要求决策助理人员高瞻远瞩,深思熟虑...

  8. Unity中的AI怪物巡逻

    Unity中的AI怪物巡逻 public Transform PoOne; public Transform PosTwo; public GameObject Enumy; public GameObject Player; void Start() { GetComponentNavMeshAgent().destination = PosTwo.position; } void Update() { if(Vector3.Distance(Player.tr

  9. 智能巡逻兵

    智能巡逻兵 一、作业要求及人工智能 这次作业的要求是做一个智能巡逻兵的小游戏。对于很多游戏来说,人工智能是不可或缺的一部分。优秀的人工智能可以让游戏更加具有挑战性,让玩家感受到更真实的游戏体验,更重要的...

  10. 巡逻机器人

    夜晚到了警察们又高兴又发愁.高兴的是下班的警察可以好好休息一下了,发愁的是上班的警察又要在外面巡逻摸黑了,又累又不安全. 我想发明一种巡逻机器人,它比我高五厘米,手长二十五分米,眼睛宽二厘米.它的肚子...

  11. 巡逻机器人

    夜晚到了警察们又高兴又发愁.高兴的是下班的警察可以好好休息一下了,发愁的是上班的警察又要在外面巡逻摸黑了,又累又不安全. 我想发明一种巡逻机器人,它比我高五厘米,手长二十五分米,眼睛宽二厘米.它的肚子...

  12. 「APIO2019」桥梁 题解

    先讲下部分分怎么搞。 有个非常暴力的暴力做法: 对于每一个询问,把边权大于 (w_j) 的边加入,并查集维护联通块即可。 时间复杂度 (mathcal{O(qm)}) ,可以过 (mathrm{Subtask 1}) 当 (t_i=2) 的时候,可以直接 kruskal 重构树,可以过 (mat...

  13. UE4 巡逻系统及AI感知组件

    UE4 巡逻系统及AI感知组件 随机巡逻和AIPerceptionComponent 随机巡逻 AI感知组件 尾言 首先创建AI行为树和黑板 自己进行命名 然后打开新建的黑板,在黑板中添加两个布尔( IsHearSomeNoise 、 IsFindPlayer )、一个向量( TargetLocation )和一个对...

  14. P3643 [APIO2016]划艇

    P3643 [APIO2016]划艇 题意 一个合法序列可表示为一个长度为 \(n\) 的序列,其中第 \(i\) 个数可以为 0 或 \([l_i,r_i]\) 中一个整数,且满足所有不为零的数组成的子序列严格上升。求合法序列方案数。 思路 朴素动态规划做法为,设 \(f_...

  15. 「APIO2018」铁人两项

    知识点:圆方树 原题面:Loj、Luogu。 简述 给定一 \(n\) 个节点 \(m\) 条边的无向图,求存在多少对有序三元组 \((s,c,f)\),满足 \(s,c,f\) 互不相同且存在一条从 \(s\) 到 \(f\) 的简单路径使得 \(c\) 在路径上出现。 \(1\le n\le 10^5\),\(1\le m...

  16. Unity学习(11)之自动巡逻兵改进

    Unity学习(11)之自动巡逻兵改进一个好的游戏必不可少的是美工资源。虽然作为程序员我们不会美工,那么能够寻找到资源就是一个重要的课程了。这周我用一些动画资源来改进自动巡逻兵的游戏。先来看一下前后变化图。这...

  17. luoguP3625 APIO2009 采油区域

    luoguP3625 APIO2009 采油区域 题面 题面 题解 套路题。 我第一想法是设 f [ i ] [ j ] [ k ] f[i][j][k] f [ i ] [ j ] [ k ] 为 ( 1 , 1 ) ? ( i , j ) (1,1)-(i,j) ( 1 , 1 ) ? ( i , j ) 的矩阵里,选了k个子矩阵,且最后一个矩阵的右下角为 ( i , j ) (

  18. LG P5445 [APIO2019]路灯

    Description 一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 $n+1$ 个停车站点,它们将街道划分成了 $n$ 条路段。每一路段都拥有一个路灯。当第 $i$ 个路灯亮起,它将照亮连接第 $i$ 与第 $i+1$ 个站点的路段。否则这...

  19. RFID巡更机怎么让枯燥的巡逻变得有趣呢?

    巡逻检查是一份看似简单而责任重大的工作,是人们人身、财产安全的一份保障。特别是在楼宇小区、石油化工领域意义重大。然而一些巡逻人员对巡逻工作有抵触心理,每年因其工作的疏忽而引发的事故不计其数。因此,作为...

  20. Luogu P5445 [APIO2019] 路灯

    很清新的DS题,话说我好久没写过DS了…… 首先我们考虑把一对路灯 (x,y) 间的答案看做点对 ((x,y)) ,那么显然有一个性质,若 (l,r) 联通,则 (u,v(lle uvle r)) 也联通 换句话说就是 ((x,y)) 为 最长的连续的1子序列 的两个端点,那么每...

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

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