运输计划

题目描述

公元 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。 接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j 个 运输计划是从 uj 号星球飞往 vj 号星球。

输出

共 1 行,包含 1 个整数,表示小 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

提示

solution:

首先，想到的是一个暴力的做法：枚举哪一条边的权值改为0，然后tarjan求LCA，算出树上最短路，统计答案。时间复杂度O（n²）,可以得到50分。11、12个点m=1，可以随便乱搞。13~16是一条链，又是求“最大值最小”，很容易想到二分答案+差分。这样子可以轻松骗到80分。 再来想正解，发现其实一棵树的情况也可以用与一条链类似的方法做。先用tarjan求出LCA，然后还是二分答案，将代价大于mid的询问视为有用询问，没用的询问不用管，差分不再是在一条链上了，要树上差分，即a[x]++,a[y]++,a[LCA(x,y)]-=2，然后递归累加a数组，就可以求出每一条边被几组有用的询问经过。为了使所有的询问代价小于等于mid，而有用询问的代价都是大于mid的，所以只有被所以有用询问经过的边才可能被变为虫洞。为了让最大的代价最小，显然应该将可能变为虫洞的边中权值最大的那条变为虫洞，这样子就可以判断答案了。 时间复杂度O（n+n lg n）=O(n lg n)，AC！

code

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstdlib> #include<cstring> #include<vector> using namespace std; int MAX,Max,num,l,r,mid,aa[1000005],qx[1000005],qy[1000005],ans,ans1,X[1000005],Y[1000005],Z[1000005],T,n,m,color[1000005],fa[1000005],qa[1000005],qb[1000005],deep[1000005]; vector<pair<int,int> > question[1000005]; vector<pair<int,pair<int,int> > > edge[1000005]; vector<pair<int,int> >::iterator beg[1000005]; bool vis[1000005]; int get(int x){ if(x==fa[x]) return x; return fa[x]=get(fa[x]); } void dfs(int u,int emperor){ color[u]=1; for(vector<pair<int,pair<int,int> > >::iterator i=edge[u].begin();i!=edge[u].end();i++) if(!color[i->first]){ deep[i->first]=deep[u]+i->second.first; dfs(i->first,emperor); fa[i->first]=u; } color[u]=2; for(vector<pair<int,int> >::iterator i=question[u].begin();i!=question[u].end();i++) if(color[i->first]==2) i->second=get(i->first); } void dfs(int u){ for(vector<pair<int,pair<int,int> > >::iterator i=edge[u].begin();i!=edge[u].end();i++){ int v=i->first; if(!vis[v]){ vis[v]=true; dfs(v); i->second.second=aa[v]; aa[u]+=aa[v]; } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<n;i++) scanf("%d%d%d",&X[i],&Y[i],&Z[i]); for(int i=1;i<=m;i++) scanf("%d%d",&qx[i],&qy[i]); for(int i=1;i<n;i++){ int x=X[i],y=Y[i],z=Z[i]; edge[x].push_back(make_pair(y,make_pair(z,0))); edge[y].push_back(make_pair(x,make_pair(z,0))); } for(int i=1;i<=m;i++){ int x=qx[i],y=qy[i]; qa[i]=x; qb[i]=y; question[x].push_back(make_pair(y,0)); question[y].push_back(make_pair(x,0)); } for(int i=1;i<=n;i++) fa[i]=i; dfs(1,1); for(int i=1;i<=n;i++) beg[i]=question[i].begin(); l=0; r=1000000000; while(l<r){ mid=(l+r)>>1; num=0; for(int i=1;i<=n;i++) aa[i]=0,vis[i]=false; MAX=0; for(int i=1;i<=n;i++) beg[i]=question[i].begin(); for(int i=1;i<=m;i++){ int x,y; x=qa[i]; y=qb[i]; if(deep[x]+deep[y]-2*deep[max(beg[x]->second,beg[y]->second)]>mid){ MAX=max(MAX,deep[x]+deep[y]-2*deep[max(beg[x]->second,beg[y]->second)]); num++; aa[x]++; aa[y]++; aa[max(beg[x]->second,beg[y]->second)]-=2; } beg[x]++; beg[y]++; } dfs(1); Max=0; for(int i=1;i<=n;i++) for(vector<pair<int,pair<int,int> > >::iterator it=edge[i].begin();it!=edge[i].end();it++) if(it->second.second==num) Max=max(Max,it->second.first); if(MAX-Max>mid) l=mid+1; else r=mid; } printf("%d\n",r); return 0; }