[BZOJ4326][codevs4632][codevs5440][UOJ#150][NOIP2015]运输计划

时间:2023-01-18 13:33:42

[BZOJ4326][codevs4632][codevs5440][UOJ#150][NOIP2015]运输计划

试题描述

公元 2044 年,人类进入了宇宙纪元。

L 国有 n 个星球,还有 n−1 条双向航道,每条航道建立在两个星球之间,这 n−1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司, 该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新, L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后,这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以*选择将哪一条航道改造成虫洞, 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

输入

第一行包括两个正整数 n,m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。

接下来 n−1 行描述航道的建设情况,其中第 i 行包含三个整数 ai,bi 和 ti,表示第 i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。数据保证 1≤ai,bi≤n 且 0≤ti≤1000。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j 个运输计划是从 uj 号星球飞往 vj号星球。数据保证 1≤ui,vi≤n

输出

输出文件只包含一个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。

输入示例


输出示例


数据规模及约定

测试点编号 n= m= 约定
1 100 1  
2 100 100 第i条航道连接i号星球与i+1号星球
3 100 100  
4 2000 1
5 1000 1000 第i条航道连接i号星球与i+1号星球
6 2000 2000 第i条航道连接i号星球与i+1号星球
7 3000 3000 第i条航道连接i号星球与i+1号星球
8 1000 1000  
9 2000 2000
10 3000 3000
11 80000 1
12 100000 1
13 70000 70000

第i条航道连接i号星球与i+1号星球

14 80000 80000 第i条航道连接i号星球与i+1号星球
15 90000 90000 第i条航道连接i号星球与i+1号星球
16 100000 100000 第i条航道连接i号星球与i+1号星球
17 80000 80000  
18 90000 90000
19 100000 100000
20 300000 300000

所有数据

    1<=ai,bi,uj,vj<=n,0<=ti<=1000

题解

留了好久的坑终于填上了。我们首先把每条链(即每个运输计划)的长度预处理出来,然后按照长度从大到小排序。

因为我们发现如果想使答案减小,一定要让最长的链变短。我们需要将所有链长相同的链进行合并(即求交,不难发现多条链只要有交集,那么交集就是一条链),然后重复一下过程:

1.) 对当前链找到它的边长最大值 mx,用 max{ 下一链长, 当前链长 - mx } 更新答案 ans;

2.) 把下一条链与当前链合并(求交),作为下一轮的当前链;

3.) 若这不是最后一条链,回到 1.)。

4.) 最后答案就是 ans。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 300010
#define maxm 600010
#define maxlog 20
#define oo 2147483647
int n, m, q, head[maxn], next[maxm], to[maxm], dist[maxm];
struct Que {
int a, b, d;
Que() {}
Que(int _1, int _2, int _3): a(_1), b(_2), d(_3) {}
bool operator < (const Que& t) const { return d > t.d; }
} qs[maxn]; void AddEdge(int a, int b, int c) {
to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;
return ;
} int dep[maxn], Dep[maxn], fa[maxlog][maxn], mx[maxlog][maxn], L[maxn], R[maxn], clo, list[maxm], cl, pos[maxn];
void build(int u) {
L[u] = ++clo; list[++cl] = u; pos[u] = cl;
for(int i = 1; i < maxlog; i++) {
int v = fa[i-1][u];
fa[i][u] = fa[i-1][v];
mx[i][u] = max(mx[i-1][u], mx[i-1][v]);
}
for(int e = head[u]; e; e = next[e]) if(to[e] != fa[0][u]) {
fa[0][to[e]] = u;
mx[0][to[e]] = dist[e];
dep[to[e]] = dep[u] + 1;
Dep[to[e]] = Dep[u] + dist[e];
build(to[e]);
list[++cl] = u;
}
R[u] = clo;
return ;
}
int Log[maxm], Lca[maxlog][maxm];
void rmq_init() {
Log[1] = 0;
for(int i = 2; i <= cl; i++) Log[i] = Log[i>>1] + 1;
for(int i = 1; i <= cl; i++) Lca[0][i] = list[i];
for(int j = 1; (1 << j) <= cl; j++)
for(int i = 1; i + (1 << j) - 1 <= cl; i++) {
int a = Lca[j-1][i], b = Lca[j-1][i+(1<<j-1)];
Lca[j][i] = dep[a] < dep[b] ? a : b;
}
return ;
}
int lca(int a, int b) {
int l = min(pos[a], pos[b]), r = max(pos[a], pos[b]), t = Log[r-l+1];
a = Lca[t][l]; b = Lca[t][r-(1<<t)+1];
return dep[a] < dep[b] ? a : b;
}
int calc(int a, int b) {
return Dep[a] + Dep[b] - (Dep[lca(a,b)] << 1);
}
int calcmx(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int Mx = 0;
for(int i = maxlog-1; i >= 0; i--) if(dep[a] - (1 << i) >= dep[b])
Mx = max(Mx, mx[i][a]), a = fa[i][a];
for(int i = maxlog-1; i >= 0; i--) if(fa[i][a] != fa[i][b])
Mx = max(Mx, max(mx[i][a], mx[i][b])),
a = fa[i][a], b = fa[i][b];
return a == b ? Mx : max(Mx, max(mx[0][a], mx[0][b]));
} bool cmp(int a, int b) { return dep[a] > dep[b]; }
bool isson(int pa, int son) { return L[pa] <= L[son] && L[son] <= R[pa]; } int main() {
n = read(); q = read();
for(int i = 1; i < n; i++) {
int a = read(), b = read(), c = read();
AddEdge(a, b, c);
}
build(1); rmq_init();
for(int i = 1; i <= q; i++) {
int u = read(), v = read();
qs[i] = Que(u, v, calc(u, v));
}
sort(qs + 1, qs + q + 1);
// for(int i = 1; i <= q; i++) printf("%d %d %d %d\n", qs[i].a, qs[i].b, qs[i].d, lca(qs[i].a, qs[i].b));
int A = qs[1].a, B = qs[1].b, ans = oo;
// printf("%d %d(%d %d)\n", qs[2].d, calcmx(A, B), A, B);
if(qs[1].d != qs[2].d || q == 1)
ans = min(ans, max(qs[2].d, qs[1].d - calcmx(A, B)));
for(int i = 2; i <= q; i++) {
int a = qs[i].a, b = qs[i].b, C = lca(A, B);
int ps[10];
ps[1] = lca(a, A); ps[2] = lca(a, B); ps[3] = lca(a, b);
ps[4] = lca(b, A); ps[5] = lca(b, B); ps[6] = lca(A, B);
sort(ps + 1, ps + 7, cmp);
int cp = unique(ps + 1, ps + 7) - ps;
A = ps[1]; B = ps[2];
bool ok = 1;
for(int j = 3; j <= cp; j++)
if(!isson(ps[j], A) || !isson(ps[j], B)) {
ok = 0; break;
}
if(!ok) break;
if(qs[i].d != qs[i+1].d || i == q)
ans = min(ans, max(qs[i+1].d, qs[1].d - calcmx(A, B)));
// printf("[%d %d]\n", A, B);
} printf("%d\n", ans); return 0;
}

2016-10-29 uoj 上自己 hack 自己成功,下面是 AC 代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 300010
#define maxm 600010
#define maxlog 20
#define oo 2147483647
int n, m, q, head[maxn], next[maxm], to[maxm], dist[maxm];
struct Que {
int a, b, d;
Que() {}
Que(int _1, int _2, int _3): a(_1), b(_2), d(_3) {}
bool operator < (const Que& t) const { return d > t.d; }
} qs[maxn]; void AddEdge(int a, int b, int c) {
to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;
return ;
} int dep[maxn], Dep[maxn], fa[maxlog][maxn], mx[maxlog][maxn], L[maxn], R[maxn], clo, list[maxm], cl, pos[maxn];
void build(int u) {
L[u] = ++clo; list[++cl] = u; pos[u] = cl;
for(int i = 1; i < maxlog; i++) {
int v = fa[i-1][u];
fa[i][u] = fa[i-1][v];
mx[i][u] = max(mx[i-1][u], mx[i-1][v]);
}
for(int e = head[u]; e; e = next[e]) if(to[e] != fa[0][u]) {
fa[0][to[e]] = u;
mx[0][to[e]] = dist[e];
dep[to[e]] = dep[u] + 1;
Dep[to[e]] = Dep[u] + dist[e];
build(to[e]);
list[++cl] = u;
}
R[u] = clo;
return ;
}
int Log[maxm], Lca[maxlog][maxm];
void rmq_init() {
Log[1] = 0;
for(int i = 2; i <= cl; i++) Log[i] = Log[i>>1] + 1;
for(int i = 1; i <= cl; i++) Lca[0][i] = list[i];
for(int j = 1; (1 << j) <= cl; j++)
for(int i = 1; i + (1 << j) - 1 <= cl; i++) {
int a = Lca[j-1][i], b = Lca[j-1][i+(1<<j-1)];
Lca[j][i] = dep[a] < dep[b] ? a : b;
}
return ;
}
int lca(int a, int b) {
int l = min(pos[a], pos[b]), r = max(pos[a], pos[b]), t = Log[r-l+1];
a = Lca[t][l]; b = Lca[t][r-(1<<t)+1];
return dep[a] < dep[b] ? a : b;
}
int calc(int a, int b) {
return Dep[a] + Dep[b] - (Dep[lca(a,b)] << 1);
}
int calcmx(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int Mx = 0;
for(int i = maxlog-1; i >= 0; i--) if(dep[a] - (1 << i) >= dep[b])
Mx = max(Mx, mx[i][a]), a = fa[i][a];
for(int i = maxlog-1; i >= 0; i--) if(fa[i][a] != fa[i][b])
Mx = max(Mx, max(mx[i][a], mx[i][b])),
a = fa[i][a], b = fa[i][b];
return a == b ? Mx : max(Mx, max(mx[0][a], mx[0][b]));
} bool cmp(int a, int b) { return dep[a] > dep[b]; }
bool isson(int pa, int son) { return L[pa] <= L[son] && L[son] <= R[pa]; }
bool on(int u, int pa, int son) { return isson(u, son) & isson(pa, u); } int main() {
n = read(); q = read();
for(int i = 1; i < n; i++) {
int a = read(), b = read(), c = read();
AddEdge(a, b, c);
}
build(1); rmq_init();
for(int i = 1; i <= q; i++) {
int u = read(), v = read();
qs[i] = Que(u, v, calc(u, v));
}
sort(qs + 1, qs + q + 1);
// for(int i = 1; i <= q; i++) printf("%d %d %d %d\n", qs[i].a, qs[i].b, qs[i].d, lca(qs[i].a, qs[i].b));
int A = qs[1].a, B = qs[1].b, ans = qs[1].d;
// printf("%d %d(%d %d)\n", qs[2].d, calcmx(A, B), A, B);
if(qs[1].d != qs[2].d || q == 1)
ans = min(ans, max(qs[2].d, qs[1].d - calcmx(A, B)));
for(int i = 2; i <= q; i++) {
int a = qs[i].a, b = qs[i].b;
int a1 = a, b1 = b, c1 = lca(a1, b1), a2 = A, b2 = B, c2 = lca(a2, b2);
if((on(a2, c1, a1) && a2 != c1) || (on(b2, c1, a1) && b2 != c1) || (on(c2, c1, a1) && c2 != a1)
|| (on(a2, c1, b1) && a2 != c1) || (on(b2, c1, b1) && b2 != c1) || (on(c2, c1, b1) && c2 != b1)
|| (on(a1, c2, a2) && a1 != c2) || (on(b1, c2, a2) && b1 != c2) || (on(c1, c2, a2) && c1 != a2)
|| (on(a1, c2, b2) && a1 != c2) || (on(b1, c2, b2) && b1 != c2) || (on(c1, c2, b2) && c1 != b2)) ;
else break;
int ps[10];
ps[1] = lca(a, A); ps[2] = lca(a, B); ps[3] = lca(a, b);
ps[4] = lca(b, A); ps[5] = lca(b, B); ps[6] = lca(A, B);
sort(ps + 1, ps + 7, cmp);
int cp = unique(ps + 1, ps + 7) - ps;
A = ps[1]; B = ps[2];
bool ok = 1;
for(int j = 3; j <= cp; j++)
if(!isson(ps[j], A) || !isson(ps[j], B)) {
ok = 0; break;
}
if(!ok) break;
if(qs[i].d != qs[i+1].d || i == q)
ans = min(ans, max(qs[i+1].d, qs[1].d - calcmx(A, B)));
if(qs[i].d != qs[i+1].d || i == q)
ans = min(ans, max(qs[i+1].d, qs[1].d - calcmx(A, B)));
// printf("[%d %d]\n", A, B);
} printf("%d\n", ans); return 0;
}

[BZOJ4326][codevs4632][codevs5440][UOJ#150][NOIP2015]运输计划的更多相关文章

  1. NOIP2015 运输计划(bzoj4326)

    4326: NOIP2015 运输计划 Time Limit: 30 Sec  Memory Limit: 128 MBSubmit: 886  Solved: 574[Submit][Status] ...

  2. bzoj 4326&colon; NOIP2015 运输计划

    4326: NOIP2015 运输计划 Time Limit: 30 Sec Memory Limit: 128 MB Description 公元 2044 年,人类进入了宇宙纪元.L 国有 n 个 ...

  3. &lbrack;NOIP2015&rsqb;运输计划 D2 T3 LCA&plus;二分答案&plus;差分数组

    [NOIP2015]运输计划 D2 T3 Description 公元2044年,人类进入了宇宙纪元. L国有n个星球,还有n-1条双向航道,每条航道建立在两个星球之间,这n-1条航道连通了L国的所有 ...

  4. NOIP2015 运输计划(二分&plus;LCA&plus;差分)

    4326: NOIP2015 运输计划 Time Limit: 30 Sec  Memory Limit: 128 MBSubmit: 308  Solved: 208[Submit][Status] ...

  5. 数据结构&lpar;树链剖分&rpar;:COGS 2109&period; &lbrack;NOIP2015&rsqb; 运输计划

    2109. [NOIP2015] 运输计划 ★★★   输入文件:transport.in   输出文件:transport.out   简单对比时间限制:1 s   内存限制:256 MB [题目描 ...

  6. BZOJ 4326 NOIP2015 运输计划 &lpar;二分&plus;树上差分&rpar;

    4326: NOIP2015 运输计划 Time Limit: 30 Sec  Memory Limit: 128 MBSubmit: 1930  Solved: 1231[Submit][Statu ...

  7. cogs2109 &lbrack;NOIP2015&rsqb; 运输计划

    cogs2109 [NOIP2015] 运输计划 二分答案+树上差分. STO链剖巨佬们我不会(太虚伪了吧 首先二分一个答案,下界为0,上界为max{路径长度}. 然后判断一个答案是否可行,这里用到树 ...

  8. LOJ2425 NOIP2015 运输计划 【二分&plus;LCA&plus;树上差分】&ast;

    LOJ2425 NOIP2015 运输计划 LINK 题意:给你一颗树,可以将任意一条边的权值变成0,然后求m条路径的长度的最小值 思路: 先二分最后的距离ans,然后我们把路程大于ans的所有路径拿 ...

  9. AC日记——&lbrack;NOIP2015&rsqb;运输计划 cogs 2109

    [NOIP2015] 运输计划 思路: 树剖+二分: 代码: #include <cstdio> #include <cstring> #include <iostrea ...

随机推荐

  1. Hadoop学习日志- install hadoop

    资料来源 : http://www.tutorialspoint.com/hadoop/hadoop_enviornment_setup.htm Hadoop 安装 创建新用户 $ su passwo ...

  2. python raise a string exception is deprecated

    python不允许raise 一个内建的string 对象.所以就崩溃,可以先将其转换成其他string,比如赋值.

  3. 学习HTML5之新特性标签一览(详细)

    HTML5又2008年诞生,HTML5大致可以等同于=html+css3+javascriptapi.... so --->支持css3强大的选择器和动画以及javascript的新的函数 先来 ...

  4. Ceph osd启动报错osd init failed &lpar;36&rpar; File name too long

    在Ceph的osd节点上,启动osd进程失败,查看其日志/var/log/ceph/ceph-osd.{osd-index}.log日志,报错如下: 2017-02-14 16:26:13.55853 ...

  5. ZJOI2008树的统计Count

    知识点-树链剖分 "在一棵树上进行路径的修改.求极值.求和":乍一看只要线段树就能轻松解决,实际上,仅凭线段树是不能搞定它的.我们需要用到一种貌似高级的复杂算法--树链剖分.   ...

  6. linux清屏命令(clear,reset)

    (1)clear 这个命令将会刷新屏幕,本质上只是让终端显示页向后翻了一页,如果向上滚动屏幕还可以看到之前的操作信息.一般都会用这个命令. (2)reset 这个命令将完全刷新终端屏幕,之前的终端输入 ...

  7. javascript OOP(下)(九)

    一.javascript模拟重载 java中根据参数类型和数量的区别来实现重载,javascript弱类型,没有直接的机制实现重载,javascript中参数类型不确定和参数个数任意,通过判断实际传入 ...

  8. 安装64位php开发环境

    最近听说PHP5.4速度很快,所以想建立一个本地环境测试下.我打算用本地windows xp sp3下安装PHP5.4.8.Apache2.4.3和Mysql5.5.28. 首先去下载PHP.Apac ...

  9. python 利用urllib 获取办公区公网Ip

    import json,reimport urllib.requestdef GetLocalIP(): IPInfo = urllib.request.urlopen("http://ip ...

  10. 软工实践-Alpha 冲刺 (8&sol;10)

    队名:起床一起肝活队 组长博客:博客链接 作业博客:班级博客本次作业的链接 组员情况 组员1(队长):白晨曦 过去两天完成了哪些任务 描述: 已经解决登录注册等基本功能的界面. 完成非功能的主界面制作 ...