CF835F Roads in the Kingdom/UOJ126 NOI2013 快餐店 树的直径

时间:2021-10-16 01:10:14

传送门——CF

传送门——UOJ


题目要求基环树删掉环上的一条边得到的树的直径的最小值。

如果直接考虑删哪条边最优似乎不太可做,于是考虑另一种想法:枚举删掉的边并快速地求出当前的直径。

对于环上的点,先把它的子树计算完毕,然后将最深的那条链接在这个点上,即记录每个点子树的最深深度,记为\(dep_i\)。然后枚举环上的节点\(x\),设\(dis_y\)表示从\(x\)开始顺时针到达\(y\)需要走多远(相当于将\(x\)和其逆时针遇到的第一个点之间的边删掉),那么当前的直径就是\(\max\limits_{dis_i < dis_j} {dep_i - dis_i + dep_j + dis_j}\),拿两个\(set\)把\(dep_i - dis_i\)、\(dep_i + dis_i\)记录起来取\(max\)。因为\(dis_i < dis_j \rightarrow dep_i - dis_i + dep_j + dis_j > dep_i + dis_i + dep_j - dis_j\),所以不会发生错位的情况。如果\(dep_i - dis_i\)和\(dep_i + dis_i\)在同一个\(i\)处取到最大值,就两个中一个选最大值、一个选次大值,两种方案取\(max\)

然后考虑换边,将枚举的点从\(x\)移到\(x\)顺时针方向的第一个点\(z\)。会发生改变的是\(dis\),设其改变到\(dis'\)。又设环长为\(cir\),那么\(dis'_x = cir - w(x,z)\),\(\forall y \neq x , dis'_y = dis_y - w(x,z)\)。所以直接修改\(dis_x\)为\(cir\)即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<set>
//This code is written by Itst
using namespace std; const int MAXN = 2e5 + 9;
struct Edge{
int end , upEd , w;
}Ed[MAXN << 1];
int head[MAXN] , N , cntEd = 1;
bool vis[MAXN]; inline void addEd(int a , int b , int c){
Ed[++cntEd] = (Edge){b , head[a] , c};
head[a] = cntEd;
} int find(int x , int uped){
vis[x] = 1;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(i != (uped ^ 1))
if(!vis[Ed[i].end]){
int t = find(Ed[i].end , i);
if(t) return t == x ? 0 : t;
}
else
return Ed[i].end;
return vis[x] = 0;
} long long sum , dp[MAXN] , len[MAXN] , cir = 1e18 , ans;
vector < int > incir;
bool pos[MAXN]; void dfs(int x , int p){
if(vis[x]) incir.push_back(x);
pos[x] = 1;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end] && Ed[i].end != p){
dfs(Ed[i].end , x);
ans = max(ans , dp[x] + dp[Ed[i].end] + Ed[i].w);
dp[x] = max(dp[x] , dp[Ed[i].end] + Ed[i].w);
}
else
if(vis[Ed[i].end] && !pos[Ed[i].end]){
len[Ed[i].end] = len[x] + Ed[i].w;
dfs(Ed[i].end , x);
}
} #define PLI pair < long long , int >
#define st first
#define nd second
set < PLI > s1 , s2;
set < PLI > :: iterator it1 , it2; void solve(){
for(int i = 0 ; i < incir.size() ; ++i){
s1.insert(PLI(dp[incir[i]] + len[incir[i]] , i));
s2.insert(PLI(dp[incir[i]] - len[incir[i]] , i));
}
for(int i = 0 ; i < incir.size() ; ++i){
it1 = --s1.end(); it2 = --s2.end();
if(it1->nd == it2->nd){
long long t = (--it1)->st + it2->st;
cir = min(cir , max(t , (++it1)->st + (--it2)->st));
}
else
cir = min(cir , it1->st + it2->st);
s1.erase(s1.find(PLI(dp[incir[i]] + len[incir[i]] , i)));
s2.erase(s2.find(PLI(dp[incir[i]] - len[incir[i]] , i)));
s1.insert(PLI(dp[incir[i]] + len[incir[i]] + sum , i));
s2.insert(PLI(dp[incir[i]] - len[incir[i]] - sum , i));
}
} int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
cin >> N;
for(int i = 1 ; i <= N ; ++i){
int a , b , c;
cin >> a >> b >> c;
addEd(a , b , c); addEd(b , a , c);
}
find(1 , 0);
for(int i = 1 ; i <= N ; ++i)
if(vis[i]){
dfs(i , 0);
break;
}
for(int i = 0 ; i < incir.size() ; ++i)
for(int j = head[incir[i]] ; j ; j = Ed[j].upEd)
if(Ed[j].end == incir[(i + 1) % incir.size()]){
sum += Ed[j].w;
if(incir.size() > 2)
break;
}
if(incir.size() == 2) sum >>= 1;
solve();
cout << max(ans , cir);
return 0;
}

CF835F Roads in the Kingdom/UOJ126 NOI2013 快餐店 树的直径的更多相关文章

  1. &lbrack;NOI2013&rsqb;快餐店 &sol; CF835F Roads in the Kingdom (基环树)

    题意 一颗基环树,选一对点使得这两个点的最短距离最大. 题解 相当于找基环树的直径,但是这个直径不是最长链,是基环树上的最短距离. 然后不会做. 然后看了ljh_2000的博客. 然后会了. 这道题最 ...

  2. BZOJ3242&sol;UOJ126 &lbrack;Noi2013&rsqb;快餐店

    本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/ ...

  3. CF835F Roads in the Kingdom

    话说这是去年大爷的一道NOIP模拟赛题,对着大爷的代码看了一堂课的我终于把这题写掉了. 本题要求在基环树给定的环上删去一条边使剩下的树的直径最小,输出这个最小直径. 那么基环树可以画成这样子的: 有一 ...

  4. bzoj 3242&colon; &lbrack;Noi2013&rsqb;快餐店 章鱼图

    3242: [Noi2013]快餐店 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 266  Solved: 140[Submit][Status] ...

  5. Codeforces 835 F&period; Roads in the Kingdom

    \(>Codeforces\space835 F. Roads in the Kingdom<\) 题目大意 : 给你一棵 \(n\) 个点构成的树基环树,你需要删掉一条环边,使其变成一颗 ...

  6. Codeforces 835 F Roads in the Kingdom&lpar;树形dp&rpar;

    F. Roads in the Kingdom(树形dp) 题意: 给一张n个点n条边的无向带权图 定义不便利度为所有点对最短距离中的最大值 求出删一条边之后,保证图还连通时不便利度的最小值 $n & ...

  7. codeforces 427 div&period;2 F&period; Roads in the Kingdom

    F. Roads in the Kingdom time limit per test 2 seconds memory limit per test 256 megabytes input stan ...

  8. Codeforces 835F Roads in the Kingdom (环套树 &plus; DP)

    题目链接 Roads in the Kingdom 题意  给出一个环套树的结构,现在要删去这个结构中的一条边,满足所有点依然连通. 删边之后的这个结构是一棵树,求所有删边情况中树的直径的最小值. 显 ...

  9. bzoj 3242&colon; &lbrack;Noi2013&rsqb;快餐店

    Description 小T打算在城市C开设一家外送快餐店.送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小T希望快餐店的地址选在离最远的顾客距离最近的地方. 快餐店的顾客分布在城 ...

随机推荐

  1. Dropbox能火,为何它的中国同行不能火?

    http://tech.163.com/15/0510/11/AP8II63H000915BF.html Dropbox能火,为何它的中国同行不能火? 2015-05-10 11:33:55 来源:  ...

  2. js 解析本地Excel文件!

    通常,一般读取Excel都是由后台来处理,不过如果需求要前台来处理,也是可以的.. 1.需要用到js-xlsx,下载地址:js-xlsx 2.demo: <!DOCTYPE html>&l ...

  3. Spark环境搭建(上)——基础环境搭建

    Spark摘说 Spark的环境搭建涉及三个部分,一是linux系统基础环境搭建,二是Hadoop集群安装,三是Spark集群安装.在这里,主要介绍Spark在Centos系统上的准备工作--linu ...

  4. Exp2 后门原理与实践-------20164325王晓蕊

    Exp2 后门原理与实践 任务一:使用netcat获取主机操作Shell,cron启动 1.windows获取linux shell 1.1 ipconfig  查看本机查看以太网适配器(8)的ipv ...

  5. Java享元模式

    定义:提供了减少对象数量从而改善应用所需的对象结构的方式 运用共享技术有效支持大量细微度的对象 类型:结构型 应用场景:系统底层的开发啊,以便解决系统的性能问题 系统有大量的相似对象,需要缓存池的场景 ...

  6. Linux软件源

    Kali科大软件源: vim /etc/apt/sources.list 下面的粘帖进去. deb http://mirrors.ustc.edu.cn/kali kali main non-free ...

  7. MVC编程模式

    MVC编程模式 MVC 是一种使用 MVC(Model View Controller 模型-视图-控制器)设计创建 Web 应用程序的模式: Model(模型)表示应用程序核心(比如数据库记录列表) ...

  8. 探索未知种族之osg类生物---呼吸分解之事件循环一

    事件循环和更新循环 终于到了我们嘴里经常念叨的事件循环.更新循环以及渲染循环了.首先我们来区分一下事件循环和渲染循环,他们两个首先是两个不同顺序执行的过程,我们有时候会用到任意node的updateC ...

  9. Final发布——视频博客

    1.视频链接 视频上传至优酷自频道,地址链接:http://v.youku.com/v_show/id_XMzk1OTIwNTUwMA==.html?spm=a2h0j.11185381.listit ...

  10. videojs 隐藏videobar

    video::-internal-media-controls-download-button { display: none; } video::-webkit-media-controls-enc ...