【NOIP15 D2T3】运输计划

Source and Judge

NOIP2015 提高组 D2T3
Uoj150
Bzoj4326
Luogu2680
Caioj1574

Problem

【Description】
公元 2044 年,人类进入了宇宙纪元。L 国有 n个星球,还有 n-1条双向航道,每条航道建立在两个星球之间,这 n-1 条 航道连通了 L 国的所有星球。

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

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

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

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?
【Input】
第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的 数量,星球从 1 到 n 编号。

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

接下来 m行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j个 运输计划是从 uj 号星球飞往 vj号星球。
【Output】
共 1 行,包含 1 个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。
【Limited conditions】

【Sample input】
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
【Sample output】
11
【Sample explanation】

Record

2h
很多变量忘记清零了……
code20min
check2h……

Analysis

请先思考后再展开

首先一眼树链剖分是没问题的
但我觉得应该会有更有意思的方法吧……不然就不做了
看了看题解,还真有
居然是树上差分!
这东西我大概知道,但是说实话我一直没有用过
然后发现我以前的猜测是错误的,它是从深度大的地方向上的(子树和)
所以能很轻松地处理路径通过量的统计问题

总结一下:

  1. 先搞一搞lca
  2. 显然最小化最大值,搞个二分
  3. 然后就优化那个被所有【需要优化的路径】经过的边中长度最大者(不是被所有经过的话,就一定不能彻底解决问题),判断是否可行

时间复杂度:O(nlogn)
那么理论上是非常快的
但是caioj和uoj都过不去……
可能是被卡栈了?不管了无伤大雅

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
void qread(int &x)
{
x=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') x=x*10+c-'0',c=getchar();
}
//*******************全局常量*******************
const int MAXN=310000;
//*******************全局定义*******************
struct Nod
{
int hou;
int dep;
int dis;
int dis2;//与父亲
Nod()
{
hou=dep=dis=dis2=0;
}
}p[MAXN];
struct Edge
{
int y,c,g;
}e[MAXN*2];
int ln=0;
void ins(int x,int y,int c)
{
e[++ln]=(Edge){y,c,p[x].hou};p[x].hou=ln;
}
int n,m;
int bin[30];
int f[MAXN][30];
//*******************实现*******************
void dfs(int x,int fa)
{
f[x][0]=fa;p[x].dep=p[fa].dep+1;
for(int i=1;bin[i]<=p[x].dep;i++) f[x][i]=f[f[x][i-1]][i-1];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
p[y].dis=p[x].dis+e[k].c;
p[y].dis2=e[k].c;
dfs(y,x);
}
}
int lca(int x,int y)
{
if(p[x].dep<p[y].dep) swap(x,y);
for(int i=20;i>=0;i--) if(bin[i]<=p[x].dep-p[y].dep) x=f[x][i];
if(x==y) return x;
for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];//上面的循环,曾经以为不用到0,还没错过……
}
struct Road
{
int x,y;
int lca,length;
}s[MAXN];
int sum[MAXN];//树上差分,与父亲
int ss;
int ans;//最长
void dfs2(int x,int fa)
{
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dfs2(y,x);sum[x]+=sum[y];
}
if(sum[x]==ss) ans=mymax(ans,p[x].dis2);
}
bool check(int mid)
{
memset(sum,0,sizeof sum);//debug
int mxl=0;ss=0;
for(int i=1;i<=m;i++)
if(s[i].length>mid)
{
mxl=mymax(mxl,s[i].length);
ss++;
sum[s[i].x]++;
sum[s[i].y]++;
sum[s[i].lca]-=2;
}
ans=0;//debug
dfs2(1,0);
return mxl-ans<=mid;
}
//*******************主函数*******************
int main()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++)
{
int x,y,c;qread(x);qread(y);qread(c);
ins(x,y,c);ins(y,x,c);
}
dfs(1,0);
for(int i=1;i<=m;i++)
{
qread(s[i].x);qread(s[i].y);
s[i].lca=lca(s[i].x,s[i].y);
s[i].length=p[s[i].x].dis+p[s[i].y].dis-2*p[s[i].lca].dis;
}
int l=0,r=300000000,ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-05/运输计划.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%