BZOJ 1912:[Apio2010]patrol 巡逻(树直径)
2024-09-05 01:34:13
1912: [Apio2010]patrol 巡逻
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
1 2
3 1
3 4
5 3
7 5
8 5
5 6
Sample Output
11
HINT
10%的数据中,n ≤ 1000, K = 1;
30%的数据中,K = 1;
80%的数据中,每个村庄相邻的村庄数不超过 25;
90%的数据中,每个村庄相邻的村庄数不超过 150;
100%的数据中,3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。
Source
分析:
k=0时显然每条边经过一次,答案为2*(n-1)
k=1时可以发现,新路连的两个端点i,j之间形成环,环上所有边都不需要经过两次,相当于k=0时的答案减去ij间距再+1(新路必须经过),显然ij距离最大时最优,故取树上最长链。
k=2时可以发现,在k=1基础上再连一条边不能直接取次长链,因为每经过k=1选取的链上的边,你将会多走2步,故将原来最长链上的边变成-1,再求最长链,在将k=1答案减去+1即可。
program pat;
type
point=^node;
node=record
x,v:longint; next:point;
end;
var
a:array[..]of point;
f1,f2,s1,s2:array[..]of longint;
n,i,m,max,k,x,y,ans:longint; p:point;
procedure add(x,y:longint);
var p:point;
begin
new(p); p^.x:=y; p^.v:=; p^.next:=a[x]; a[x]:=p;
end;
procedure dfs(x,e:longint);
var p:point; y:longint;
begin
s1[x]:=x; s2[x]:=x;
new(p); p:=a[x];
while p<>nil do
begin
y:=p^.x;
if y=e then begin p:=p^.next; continue; end;
dfs(y,x);
if f1[y]+p^.v>f1[x] then
begin
f2[x]:=f1[x]; s2[x]:=s1[x];
f1[x]:=f1[y]+p^.v; s1[x]:=y;
end
else
if f1[y]+p^.v>f2[x] then
begin
f2[x]:=f1[y]+p^.v; s2[x]:=y;
end;
p:=p^.next;
end;
if f1[x]+f2[x]>f1[max]+f2[max] then
max:=x;
end;
procedure work(x:longint);
var p:point; y:longint;
begin
new(p); p:=a[x];
while p<>nil do
begin
y:=p^.x;
if y=s1[x] then begin p^.v:=-; work(y); break; end;
p:=p^.next;
end;
end;
begin
assign(input,'pat.in');reset(input);
assign(output,'pat.out');rewrite(output);
readln(n,k);
for i:= to n- do
begin
readln(x,y); add(x,y); add(y,x);
end;
ans:=*(n-); max:=; f1[]:=; f2[]:=;
dfs(,);
ans:=ans-f1[max]-f2[max]+;
if k= then writeln(ans) else
begin
fillchar(f1,sizeof(f1),);
fillchar(f2,sizeof(f2),);
new(p); p:=a[max];
while p<>nil do
begin
y:=p^.x;
if (y=s1[max])or(y=s2[max]) then p^.v:=-;
p:=p^.next;
end;
work(s1[max]); work(s2[max]); max:=;
dfs(,);
ans:=ans-f1[max]-f2[max]+;
writeln(ans);
end;
close(input); close(output);
end.
最新文章
- 整理react native的资料
- 用C++实现的SDK跨平台心得体会
- Python第十二章正则表达式
- Ruby On Rails环境搭建
- poj1992 数论
- SQL Server :Stored procedures存储过程初级篇
- JavaScript的检测属性、属性特性、枚举属性
- Python中的迭代器和生成器
- php读取memcache二进制数据
- Linux 桌面玩家指南:17. 在 Ubuntu 中使用 deepin-wine,解决一些依赖 Windows 的痛点问题
- IDEA远程调试监控端口
- pandas(DataFrame)
- 1005 Spell It Right (20 分)
- Linux at命令详解
- POJ 1141 Brackets Sequence(括号匹配二)
- ubuntu下安装和破解navicat的方法
- Java传统下载和SpringMVC下载
- Array.reduce()方法的使用
- node定时任务——node-schedule模块使用说明
- Django rest_framewok框架的基本组件
热门文章
- BZOJ3671: [Noi2014]随机数生成器(贪心)
- DNS介绍与安装使用
- Linux基础知识随笔记
- python__高级 : 类的__getattribute__ 方法
- anaconda+jupyter notebook 安装配置
- C指针——简单总结
- POJ 2891 中国剩余定理(不互素)
- 队列--数据结构与算法JavaScript描述(5)
- 笔记-爬虫-scrapy-srcapy-redis组件
- 9,K-近邻算法(KNN)