洛谷 P2680 NOIP2015提高组 运输计划 题解【tarjan】【二分答案】【LCA】
点击量:749
非常的卡常数? 拿了好长时间的95分。。
题目描述
公元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 的物流公司完成阶段性工作所需要的最短时间。
样例输入
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5样例输出11
样例解释:
将第 1 条航道改造成虫洞: 则三个计划耗时分别为:11,12,11,故需要花费的时间为 12。
将第 2 条航道改造成虫洞: 则三个计划耗时分别为:7,15,11,故需要花费的时间为 15。
将第 3 条航道改造成虫洞: 则三个计划耗时分别为:4,8,11,故需要花费的时间为 11。
将第 4 条航道改造成虫洞: 则三个计划耗时分别为:11,15,5,故需要花费的时间为 15。
将第 5 条航道改造成虫洞: 则三个计划耗时分别为:11,10,6,故需要花费的时间为 11。
故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性工作的耗时最短,需要花费的时间为 11。
测试数据及约定:
测试点编号 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
首先这个题看上去送了很多分,首先有40分的链,和20分的m=1,这60分是很好拿的,前40分在链上做差分再存一下状态就可以了,后20分直接在这条线路上枚举删掉最长边。
正确算法:我们需要找的是一条边,把这条边的权值改为0,使最长链最短。(咦这不是二分答案吗)
但是需要注意一点,如果直接改变最长链上的最长边,使最长链变得尽可能短,但此时次长链可能没有改变,所以不能直接利用贪心做,接下来我们介绍二分答案的过程。
二分答案的上界是最长链的长度,如果删掉的边权为0,答案就是这个,因此把这个作为枚举边界。而我们也可以将下界优化一下,优化到最长链减最长边。二分答案中检验的值,是可容纳的最长时间,对大于mid的链上,我们还需要找一条边,使得所有大于mid的链都经过这条边。(如果找不到一条这样的边,说明mid不合法,直接return false;)。然后在所有满足条件的边中,枚举找到边权最大的边,用最长链减去这条边作为待检验答案。如果仍然大于mid,则mid不合法,如果小于mid,则合法,return false。直到枚举到一个mid使得不能有更优解让mid-1合法。
还有一个优化是求树上两点之间的距离,如果其中一个点是另一个点的祖先,那么可以用深度较大的节点到根节点的距离(这个距离是可以预处理出来的)减去深度较浅的根节点距离。如果不是祖先关系,则用它们到根节点的距离之和减去二倍的LCA到根节点的距离,也就是前缀和的思想。
Code:
#include<cstdio>
#include<cstring>
#include<iostream>
struct node
{
int n,v,ext;
node *nxt;
node (int n,int v)
{
this->n=n;
this->v=v;
nxt=NULL;
}
node()
{
nxt=NULL;
}
};
node head[300010],*tail[300010];
struct Node
{
int n,cnt;
bool used;
Node *nxt;
Node(int n,int cnt)
{
this->cnt=cnt;
this->n=n;
nxt=NULL;
}
Node()
{
nxt=NULL;
}
};
Node Head[300010],*Tail[300010];
int s[300010];
std::pair<int,int> fa[300010];//fa是直接父亲和到直接父亲的距离
int d[300010];
int n,m,r=0;
bool vis[300010],used[300010],Used[300010];
struct Ask
{
int s,t;
int ans,anc;
Ask(int s,int t)
{
this->s=s;
this->t=t;
}
Ask(){}
}ask[300010];
int my_find(int x)
{
if(s[x]==x)
return x;
return s[x]=my_find(s[x]);
}
int up[300010];//到根结点的距离(前缀和思想)
int query(int x,int y,int lca)
{
return up[x]+up[y]-2*up[lca];
}
void tarjan(int x,int from)
{
vis[x]=true;
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(Used[p->n])
continue;
up[p->n]=up[x]+p->v;
Used[p->n]=true;
fa[p->n].first=x;
fa[p->n].second=p->v;
tarjan(p->n,x);
}
Node *P=&Head[x];
while(P->nxt!=NULL)
{
P=P->nxt;
if(vis[P->n]&&!used[P->cnt])
{
used[P->cnt]=true;
ask[P->cnt].anc=my_find(P->n);
ask[P->cnt].ans=query(P->n,x,ask[P->cnt].anc);//求这条链的长度
if(ask[P->cnt].ans>r)
r=ask[P->cnt].ans;
}
}
s[x]=from;
}
int minn=999999999,delta=0;//minn一定要大于300000000,不然常数就算优化了也会卡数据大小。
int tmp=0,longest=0,maxx=0;
void DFs(int x)
{
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(used[p->n])
continue;
used[p->n]=true;
DFs(p->n);
d[x]+=delta;
delta=0;
}
delta+=d[x];//这里是差分的做法
if(delta==tmp)
if(longest-fa[x].second<minn)
minn=longest-fa[x].second;
return;
}
bool check(int mid)
{
memset(d,0,sizeof(d));
tmp=0;
for(int i=1;i<=m;i++)//打差分
if(ask[i].ans>mid)
{
d[ask[i].s]++;
d[ask[i].t]++;
d[ask[i].anc]-=2;
tmp++;
}
minn=999999999;
memset(used,0,sizeof(used));
delta=0;
used[1]=true;
DFs(1);
if(minn>mid)
return false;
return true;
}
void work()
{
for(int i=1;i<=m;i++)
if(ask[i].ans>longest)//求最长链,优化二分下界
longest=ask[i].ans;
int l=longest-maxx,mid;
while(l<r)
{
mid=l+r>>1;
if(check(mid))
r=mid;
else
l=mid+1;
}
printf("%d\n",l);
return;
}
int read()//读入优化
{
char c=getchar();int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x;
}
int main()
{
//freopen("transport.in","r",stdin);
up[0]=0;
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
memset(used,0,sizeof(used));
memset(Used,0,sizeof(Used));
int u,v,w;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
s[i]=i;
tail[i]=&head[i];
Tail[i]=&Head[i];
}
for(int i=1;i<n;i++)
{
u=read();
v=read();
w=read();
//scanf("%d%d%d",&u,&v,&w);
tail[u]->nxt=new node(v,w);
tail[u]=tail[u]->nxt;
tail[v]->nxt=new node(u,w);
tail[v]=tail[v]->nxt;
if(w>maxx)
maxx=w;
}
for(int i=1;i<=m;i++)
{
u=read();
v=read();
//scanf("%d%d",&u,&v);
ask[i]=Ask(u,v);//初始化询问
Tail[u]->nxt=new Node(v,i);
Tail[u]=Tail[u]->nxt;
Tail[v]->nxt=new Node(u,i);
Tail[v]=Tail[v]->nxt;
}
Used[1]=true;
tarjan(1,1);//假定1为根节点
work();
return 0;
}
… [Trackback]
[…] Find More Info here on that Topic: wjyyy.top/343.html […]
… [Trackback]
[…] Read More here on that Topic: wjyyy.top/343.html […]
… [Trackback]
[…] Find More Info here to that Topic: wjyyy.top/343.html […]