Noip2015Day2T3 运输计划
2024-09-05 14:09:52
problem
一棵n个点带边权的树,有m个条路径。选择一条边,将其权值变为0,使得长度最长的路径长度最小。求该长度最小为多少。
solution
其实仔细一想并不难。
删除一条边会导致所有经过这条边的路径长度减少该边长度。所有没经过这条边的路径长度不变。
所以我们只需要知道没经过该边的路径中的长度最大值,以及经过该边的路径中长度最大值。
显然经过该边的路径长度最大值我们可以当做最长路径的最大值。
现在只要对于每条边都能够计算出没经过该边的路径长度最大值即可。
我们发现并不需要对于每条边都求出该值。
因为删除的边肯定位于最长路径上。
然后我们就把最长路径扯平。并对上面的边进行编号。
如图,对于\(S-T\)这条路径,会在删除\(1,4,5\)这三条边时产生贡献。所以我们只要用两个数组分别记录出前缀最大值和后缀最大值即可。
然后枚举删除的边,记录最优答案。
code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 300100,logN = 20;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
struct node {
int u,v,nxt,w,bz;
}e[N << 1];
int head[N],ejs;
void add(int u,int v,int w) {
e[++ejs].v = v;e[ejs].u = u;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
int id[N],cnt,dis[N];
int DFS(int u,int V,int fa) {
if(u == V) {
id[u] = ++cnt;return 1;
}
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(v == fa) continue;
if(DFS(v,V,u)) {
id[u] = ++cnt;
e[i].bz = 1;
return 1;
}
}
return 0;
}
void mark(int u,int p) {
id[u] = p;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(id[v]) continue;
mark(v,p);
}
}
int lca[N][21],dep[N];
void get_lca(int u,int fa) {
dep[u] = dep[fa] + 1;
for(int i = 1;i <= logN;++i) lca[u][i] = lca[lca[u][i - 1]][i - 1];
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(v == fa) continue;
dis[v] = dis[u] + e[i].w;
lca[v][0] = u;
get_lca(v,u);
}
}
int LCA(int x,int y) {
if(dep[x] < dep[y]) swap(x,y);
for(int i = logN;i >= 0;--i)
if(dep[lca[x][i]] >= dep[y]) x = lca[x][i];
for(int i = logN;i >= 0;--i)
if(lca[x][i] != lca[y][i]) x = lca[x][i],y = lca[y][i];
if(x != y) return lca[x][0];
return x;
}
int mx1[N],mx2[N];
struct QUE {
int s,t,len;
}Q[N];
int main() {
int mxx = 0;
int n = read(),m = read();
for(int i = 1;i < n;++i) {
int u = read(),v = read(),w = read();
add(u,v,w);add(v,u,w);
}
get_lca(1,0);
int S = 0,T = 0;
for(int i = 1;i <= m;++i) {
Q[i].s = read();Q[i].t = read();
Q[i].len = dis[Q[i].s] + dis[Q[i].t] - dis[LCA(Q[i].s,Q[i].t)] * 2;
if(Q[i].len > mxx) {
mxx = Q[i].len;
S = Q[i].s;T = Q[i].t;
}
}
DFS(S,T,0);
for(int i = 1;i <= n;++i) {
if(id[i]) {
mark(i,id[i]);
}
}
for(int i = 1;i <= m;++i) {
int s = Q[i].s,t = Q[i].t;
int l = id[s],r = id[t];
if(l > r) swap(l,r);
mx1[l - 1] = max(mx1[l - 1],Q[i].len);
mx2[r] = max(mx2[r],Q[i].len);
}
for(int i = cnt;i >= 0;--i) {
mx1[i] = max(mx1[i],mx1[i + 1]);
}
for(int i = 1;i <= cnt;++i)
mx2[i] = max(mx2[i],mx2[i - 1]);
int ans = 1e9;
for(int i = 1;i <= ejs;++i) {
if(e[i].bz) {
int l = id[e[i].u],r = id[e[i].v];
if(l > r) swap(l,r);
int k = max(max(mx1[l],mx2[l]),mxx - e[i].w);
ans = min(ans,k);
}
}
cout<<(ans == 1e9 ? 0 : ans);
return 0;
}
最新文章
- apache+php 安装
- DragLayout: QQ5.0侧拉菜单的新特效
- 使用jQuery的Scrollify插件实现鼠标滚轮或者手势滑动到页面下一节点部分
- text-align:justify_内容居中对齐
- UVa 12716 (GCD == XOR) GCD XOR
- java 小结2 多态问题和容器介绍
- 【03】尽可能使用const
- Oops信息及栈回溯
- Mac下一个svn提交.a文件
- android代码签名和混乱的包装
- java虚拟机概述
- error:Unterminated &;lt;form:form tag
- Linux 系统进程相关命令
- 理解jsonp劫持漏洞
- C++面试基础概念之动态库篇
- SharedPreferences解析
- Request.UrlReferrer注意点
- windows配置教程
- HBase的几个实示例
- 长时间没有操作putty就会断开连接是怎么回事?
热门文章
- uml统一建模语言学习笔记(一)
- c#使用CefSharp开发winform——环境搭建
- VS2017初学者如何打开右侧的解决方案资源管理器
- 10-Node.js学习笔记-异步函数
- mysql分组报错Expression #1 of SELECT list is not in GROUP BY clause and contains nonaggregated column
- 2019-2020-1 20199305《Linux内核原理与分析》第八周作业
- FIRST 集与 FOLLOW 集
- jquery使用on()方法绑定的事件被执行多次的问题
- mysql 数据误删恢复
- 对象流,它们是一对高级流,负责即将java对象与字节之间在读写的过程中进行转换。 * java.io.ObjectOutputStream * java.io.ObjectInputStream