首页 > 代码库 > 洛谷——P2680 运输计划
洛谷——P2680 运输计划
https://www.luogu.org/problem/show?pid=2680
题目背景
公元 2044 年,人类进入了宇宙纪元。
题目描述
L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物
流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?
输入输出格式
输入格式：
输入文件名为 transport.in。
第一行包括两个正整数 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
说明
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
先求出每个点到根的dis，然后找运输路径的重叠部分，二分求最优解
树上查分找重边，满足重编的情况下，如果该边除去会比一条都不除-二分值 大，就使ans减小
1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 5 using namespace std; 6 7 const int N(300000+5); 8 const int M(300000+5); 9 int n,m,u,v,w; 10 11 int head[N],sumedge; 12 struct Edge 13 { 14 int v,next,w; 15 Edge(int v=0,int next=0,int w=0): 16 v(v),next(next),w(w){} 17 }edge[N<<1]; 18 void ins(int u,int v,int w) 19 { 20 edge[++sumedge]=Edge(v,head[u],w); 21 head[u]=sumedge; 22 } 23 24 int dis[N],size[N],deep[N],dad[N],top[N]; 25 void DFS(int x) 26 { 27 size[x]=1;deep[x]=deep[dad[x]]+1; 28 for(int i=head[x];i;i=edge[i].next) 29 { 30 int v=edge[i].v; 31 if(dad[x]==v) continue; 32 dis[v]=dis[x]+edge[i].w; 33 dad[v]=x; DFS(v);size[x]+=size[v]; 34 } 35 } 36 void DFS_(int x) 37 { 38 int t=0; if(!top[x]) top[x]=x; 39 for(int i=head[x];i;i=edge[i].next) 40 { 41 int v=edge[i].v; 42 if(dad[x]!=v&&size[t]<size[v]) t=v; 43 } 44 if(t) top[t]=top[x],DFS_(t); 45 for(int i=head[x];i;i=edge[i].next) 46 { 47 int v=edge[i].v; 48 if(dad[x]!=v&&t!=v) DFS_(v); 49 } 50 } 51 int LCA(int x,int y) 52 { 53 for(;top[x]!=top[y];x=dad[top[x]]) 54 if(deep[top[x]]<deep[top[y]]) swap(x,y); 55 return deep[x]<deep[y]?x:y; 56 } 57 58 struct Plan 59 { 60 int lca,tim,u,v; 61 Plan(int u=0,int v=0,int lca=0,int tim=0): 62 u(u),v(v),lca(lca),tim(tim){} 63 }plan[M]; 64 65 int l,r,mid,ans,MAX,tot,cnt[N]; 66 void DFS_cnt(int x) 67 { 68 for(int i=head[x];i;i=edge[i].next) 69 { 70 int v=edge[i].v; 71 if(dad[x]==v) continue; 72 DFS_cnt(v); cnt[x]+=cnt[v]; 73 } 74 } 75 bool check(int x) 76 { 77 memset(cnt,0,sizeof(cnt)); tot=0; 78 for(int i=1;i<=m;i++) 79 { 80 if(plan[i].tim<=x) continue; 81 tot++; 82 cnt[plan[i].u]++; 83 cnt[plan[i].v]++; 84 cnt[plan[i].lca]-=2; 85 } 86 DFS_cnt(1); 87 for(int i=1;i<=n;i++) 88 if(cnt[i]==tot&&dis[i]-dis[dad[i]]>=MAX-x) return true; 89 return false; 90 } 91 92 int main() 93 { 94 scanf("%d%d",&n,&m); 95 for(int i=1;i<n;i++) 96 { 97 scanf("%d%d%d",&u,&v,&w); 98 ins(u,v,w); ins(v,u,w); 99 }100 DFS(1);DFS_(1);101 for(int i=1;i<=m;i++)102 {103 scanf("%d%d",&u,&v);104 int lca=LCA(u,v),tim=dis[u]+dis[v]-(dis[lca]<<1);105 plan[i]=Plan(u,v,lca,tim);106 MAX=max(MAX,tim);107 }108 for(r=MAX+1;l<=r;)109 {110 mid=l+r>>1;111 if(check(mid))112 {113 ans=mid;114 r=mid-1;115 }116 else l=mid+1;117 }118 printf("%d",ans);119 return 0;120 }
洛谷——P2680 运输计划