首页 > 代码库 > 【树链剖分】UOJ150-Transportation Plan
【树链剖分】UOJ150-Transportation Plan
【题目大意】
公元 2044 年，人类进入了宇宙纪元。L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 tj，并且任意两艘飞船之间不会产生任何干扰。为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。如果小 P 可以自由选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？
【思路】
☆
一个优化：容易知道选择的航道一定在最长航道上。求LCA的时候直接可以处理出长度，不需要用线段树……
1 #include<bits/stdc++> 2 using namespace std; 3 const int MAXN=300000+50; 4 const int INF=0x7fffffff; 5 vector<int> E[MAXN]; 6 int n,m,dep[MAXN],fa[MAXN],size[MAXN],son[MAXN],top[MAXN]; 7 int sum[MAXN],que[MAXN]; 8 int maxlen,maxpos; 9 10 void dfs1(int u,int father,int depth) 11 { 12 fa[u]=father; 13 dep[u]=depth; 14 size[u]=1; 15 son[u]=-1; 16 for (int i=0;i<E[u].size();i++) 17 { 18 int v=E[u][i]; 19 if (v==fa) continue; 20 dfs(v,u,depth+1); 21 if (son[u]==-1 || size[v]>size[son[u]]) son[u]=v; 22 } 23 } 24 25 void dfs2(int u,int utop) 26 { 27 top[u]=utop;s 28 if (son[u]!=-1) dfs2(son[u],utop); 29 for (int i=0;i<E[u].size();i++) 30 { 31 int v=E[u][i]; 32 if (v==son[u] || v==fa[u]) continue; 33 dfs2(v,v); 34 } 35 } 36 37 int lca(int x,y) 38 { 39 int ret=0; 40 while (top[x]!=top[y]) 41 { 42 if (dep[top[u]]<dep[top[v]]) swap(u,v); 43 u=fa[top[u]]; 44 } 45 return dep[u]<dep[v]?u:v; 46 } 47 48 void dfs(int u) 49 { 50 for (int i=0;i<E[u].size();i++) 51 { 52 int v=E[u][i]; 53 if (v==fa[u]) continue; 54 dfs(v); 55 sum[u]+=sum[v]; 56 } 57 } 58 59 void check(int x) 60 { 61 int d=0,p=0; 62 //d记录当前x和最长的路径长的最大差值 63 //p记录总共有几条边要比x长 64 if (maxlen<=x) return 1; 65 memset(sum,0,sizeof(sum)); 66 for (int i=1;i<=m;i++) 67 if (task[i].d>x) 68 { 69 sum[task[i].u]++; 70 sum[task[i].v]++; 71 sum[task[i].g]-=2; 72 p++; 73 d=max(d,task[i].d-x); 74 } 75 dfs(task[maxdis].g); 76 for (int i=1;i<=cnt;i++) 77 { 78 if (sum[task[i].u]==p && sum[task[i].v]==p && task[i].d>d) 79 } 80 } 81 82 void init() 83 { 84 scanf("%d%d",&n,&m); 85 for (int i=1;i<n;i++) 86 { 87 int u,v,w; 88 scanf("%d%d%d",&u,&v,&w); 89 E[u].push_back(v); 90 } 91 dfs1(1,0,1); 92 dfs2(1,1); 93 maxlen=0; 94 for (int i=1;i<=m;i++) 95 { 96 scanf("%d%d",&task[i].u,task[i].v); 97 task[i].g=lca(task[i].u,task[i].v); 98 task[i].d=dep[task[i].u]+dep[task[i].v]-2*dep[task[i].g]+1; 99 if (task[i].d>maxlen)100 {101 maxlen=task[i].d;102 maxdis=i;103 }104 }105 }106 107 void bi()108 {109 int lb=0,ub=INF;110 while (lb<rb-1)111 {112 int mid=(l+r)>>1;113 if (check(mid)) ub=mid;114 else lb=mid;115 }116 return ub;117 }118 119 int main()120 {121 init();122 bi();123 return 0;124 }
【树链剖分】UOJ150-Transportation Plan
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。