Luogu 3629 [APIO2010]巡逻
2024-10-19 04:27:20
先考虑$k = 1$的情况,很明显每一条边都要被走两遍,而连成一个环之后,环上的每一条边都只要走一遍即可,所以我们使这个环的长度尽可能大,那么一棵树中最长的路径就是树的直径。
设直径的长度为$L$,答案就是$2(n - 1) - L + 1 = 2n - L - 1$。
考虑$k = 2$的情况,发现第一条边一定还是要把直径练成一个环,而第二条边是要再求一个类似于直径的东西,具体来说,可以把原来直径(记为$L_{1}$)上的每一条边的边权取为$-1$,然后再求一遍直径(记为$L_{2}$),这样子的话答案就是$2(n - 1) - (L_{1} - 1) - (L_{2} - 1) = 2n - L_{1} - L_{2}$。发现这样做之后如果第二条直径上包含着第一条直径上的部分,那么重叠的部分就被重新加了回来,所以这样子求出来的答案就是最后的答案。
由于可以在同一个点连边,那么$L_{2}$至少要为$0$。
注意第二次求直径的时候要使用树形$dp$,两次$bfs$的方法会挂,因为边带负权之后会相当于把之前带正权的边的贡献减掉,所以第一次求出来的一端并不一定是直径的一个端点。
时间复杂度$O(n)$。
Code:
#include <cstdio>
#include <cstring>
using namespace std; const int N = 1e5 + ;
const int inf = << ; int n, m, tot = , head[N];
int root, eid[N], dis[N], ans = ;
int f[N], d[N]; struct Edge {
int to, nxt, val;
} e[N << ]; inline void add(int from, int to) {
e[++tot].to = to;
e[tot].val = ;
e[tot].nxt = head[from];
head[from] = tot;
} inline void read(int &X) {
X = ; char ch = ; int op = ;
for(; ch > ''|| ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline void chkMax(int &x, int y) {
if(y > x) x = y;
} void dfs(int x, int fat) {
dis[x] = dis[fat] + ;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(y == fat) continue;
eid[y] = i ^ ;
dfs(y, x);
}
} void dfs2(int x, int fat) {
bool flag = ;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(y == fat) continue;
flag = ;
dfs2(y, x);
chkMax(ans, d[y] + e[i].val + d[x]);
chkMax(d[x], d[y] + e[i].val);
}
if(!flag) d[x] = ;
} int main() {
read(n), read(m);
for(int x, y, i = ; i < n; i++) {
read(x), read(y);
add(x, y), add(y, x);
} dis[] = -;
dfs(, );
dis[root = n + ] = -inf;
for(int i = ; i <= n; i++)
if(dis[i] > dis[root]) root = i; dfs(root, ); /* for(int i = 1; i <= n; i++)
printf("%d ", dis[i]);
printf("\n"); */ if(m == ) {
for(int i = ; i <= n; i++)
chkMax(ans, dis[i]);
printf("%d\n", * n - - ans);
return ;
} int pnt = n + ;
for(int i = ; i <= n; i++)
if(dis[pnt] < dis[i]) pnt = i; for(int x = pnt; x != root; x = e[eid[x]].to)
e[eid[x]].val = e[eid[x] ^ ].val = -; memset(f, , sizeof(f));
memset(d, , sizeof(d));
ans = ;
dfs2(root, ); printf("%d\n", * n - dis[pnt] - ans);
return ;
}
最新文章
- Java并发编程核心方法与框架-Future和Callable的使用
- 单调队列 I
- ASP.NET MVC 中将数据从View传递到控制器中的三种方法(表单数据绑定)
- Swift实战-QQ在线音乐(第二版)
- win7下python安装pyquery
- 将现有Ubuntu系统做成LiveCD
- [STOI2014]舞伴(dp)
- PL/SQL 基础编程
- 一个简单顺序表的C++实现
- 【解惑】剖析float型的内存存储和精度丢失问题
- oracle数据库一些用户管理语句
- 整理关于web项目如何防止CSRF和XSS攻击的方法
- .Net Core下 Redis的String Hash List Set和Sorted Set的例子
- tomcat如何路由映射网址
- 使用Docker安装SonarQube
- 【转】【Android】1分钟不用改任何代码在Eclipse中使用AAR
- nodejs:导出Excel和解析导入的Excel
- el表达式用==和eq的注意事项
- Delphi 三层TDataSetProvider
- Docker学习笔记 ---存储与管理
热门文章
- PHP Smarty无法解析模板文件
- LeetCode 293. Flip Game
- To Java程序员:切勿用普通for循环遍历LinkedList(转)
- poj 1201 Intervals——差分约束裸题
- the virtual machine is configured for 64-bit guest operating systems
- 机器学习:SVM(核函数、高斯核函数RBF)
- windows下python访问ipv6报错
- 2015.3.12Arinc424 Tools中SiniArincCls.csParserFile(string sFile)函数正则表达式理解
- hadoop再次集群搭建(2)-配置免秘钥ssh登录
- 如何在Eclipse下查看JDK源代码以及java源代码阅读方法(转载)