首页 > 其他 > 详细

[树上倍增+二分答案][NOIP2012]运输计划

时间:2018-05-21 21:01:06      阅读:351      评论:0      收藏:0      [点我收藏+]

题目背景

公元 2044 年,人类进入了宇宙纪元。

题目描述

公元 2044 年,人类进入了宇宙纪元。

L 国有 nn 个星球,还有 n-1n1 条双向航道,每条航道建立在两个星球之间,这 n-1n1 条航道连通了 LL 国的所有星球。

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

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

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

如果小 P 可以自由选择将哪一条航道改造成虫洞, 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

输入输出格式

输入格式:

 

第一行包括两个正整数 n, mn,m ,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 11 到 nn 编号。

接下来 n-1n1 行描述航道的建设情况,其中第 ii 行包含三个整数 a_i, b_iai?,bi? 和 t_iti? ,表示第 ii 条双向航道修建在 a_iai? 与 b_ibi? 两个星球之间,任意飞船驶过它所花费的时间为 t_iti? 。数据保证 1 \leq a_i,b_i \leq n1ai?,bi?n 且 0 \leq t_i \leq 10000ti?1000 。

接下来 mm 行描述运输计划的情况,其中第 jj 行包含两个正整数 u_juj? 和 v_jvj? ,表示第 jj 个运输计划是从 u_juj? 号星球飞往 v_jvj?号星球。数据保证 1 \leq u_i,v_i \leq n1ui?,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



二分移动所需的时间,在二分出的时间里用树上倍增检验能否实现
看了题解还是调到吐血,最后发现m放在n后面直接读入了..
代码:
  1 #include<algorithm>
  2 #include<cstdio>
  3 #include<cstring>
  4 
  5 const int Maxv = 50005; 
  6 int Book[Maxv], Head[Maxv], f[Maxv][20], st[Maxv][20], Top[Maxv], Tdis[Maxv], q[Maxv], rnum, tail, cnt, n, m; 
  7 bool lea[Maxv], vis[Maxv], fs; 
  8 
  9 struct Node{
 10     int u, v, w, next; 
 11 }e[Maxv << 2]; 
 12 
 13 struct Army{
 14     int Rest, Top; 
 15 }army[Maxv]; 
 16 
 17 int read(){
 18     int x = 0, f = 1; 
 19     char ch = getchar(); 
 20     while (ch < 0 || ch > 9) {
 21         if (ch == -) {
 22             f = -1; 
 23         }
 24         ch = getchar(); 
 25     }
 26     while (ch >= 0 && ch <= 9) {
 27         x = x * 10 + ch - 0; 
 28         ch = getchar(); 
 29     }
 30     return x * f; 
 31 }
 32 
 33 void Add_Edge(int u, int v, int w){
 34     cnt++; 
 35     e[cnt].v = v; 
 36     e[cnt].w = w; 
 37     e[cnt].next = Head[u]; 
 38     Head[u] = cnt; 
 39 }
 40 
 41 void Add(int u, int v, int w){
 42     Add_Edge(u, v, w); 
 43     Add_Edge(v, u, w); 
 44 }
 45 
 46 inline bool Cmp(int a, int b){
 47     return a > b;   
 48 }
 49 inline bool Cmpmin(Army a, Army b){
 50     return a.Rest < b.Rest; 
 51 }
 52 
 53 inline bool Cmpmax(Army a, Army b){
 54     return a.Rest > b.Rest; 
 55 }
 56 
 57 void dfs(int u, int father){
 58     for (int i = Head[u]; i; i = e[i].next) {
 59         int v = e[i].v; 
 60         if (v == father) {
 61             continue; 
 62         }
 63         f[v][0] = u; 
 64         st[v][0] = e[i].w; 
 65         dfs(v, u); 
 66     }
 67 }//预处理倍增
 68 
 69 void RMQ(){
 70     for (int j = 1; j <= 18; j++) {
 71         for (int i = 1; i <= n; i++) {
 72             f[i][j] = f[ f[i][j - 1] ][j - 1]; 
 73             st[i][j] = st[i][j - 1] + st[ f[i][j - 1] ][j - 1]; 
 74         }
 75     }
 76 }//预处理倍增
 77 
 78 void dfs1(int u, int father, int topf, int dist){
 79     Top[u] = topf; 
 80     Tdis[u] = dist; 
 81     bool ft = false; 
 82     for (int i = Head[u]; i; i = e[i].next) {
 83         int v = e[i].v; 
 84         if (v == father) {
 85             continue; 
 86         }
 87         ft = true; 
 88         dfs1(v, u, topf, dist); 
 89     }
 90     if (!ft) {
 91         lea[u] = true; //标记叶子节点
 92     }
 93 }
 94 
 95 void dfs2(int u, int father){
 96     if (lea[u]) {
 97         fs = true; 
 98         return; 
 99     }
100     for (int i = Head[u]; i; i = e[i].next) {
101         int v = e[i].v; 
102         if (v == father) {
103             continue; 
104         }
105         else if (vis[v]) {
106             continue; 
107         }
108         dfs2(v, u); 
109         if (fs) {
110             return; 
111         }
112     }
113 }
114 
115 inline bool Look(int v){
116     fs = false; 
117     dfs2(v, f[v][0]); 
118     return fs; 
119 }
120 
121 inline bool judge(int mid){
122     memset(vis, false, sizeof(vis)); 
123     memset(q, 0, sizeof(q)); 
124     memset(army, 0, sizeof(army)); 
125     rnum = 0; 
126     tail = 0; 
127     for (int i = 1; i <= m; i++) {
128         int tim = mid; 
129         int now = Book[i]; 
130         bool syst = false; 
131         while (1) {
132             for (int j = 18; j >= 0; j--) {
133                 if (f[now][j] && st[now][j] <= tim) {
134                     tim -= st[now][j]; 
135                     now = f[now][j];  //向上跳
136                     break; 
137                 }
138                 if (j == 0 || now == 1) {
139                     syst = true; 
140                     break; //停止条件
141                 }
142             }
143             if (syst) {
144                 break; 
145             }
146         }
147         if (now == 1) {
148             army[++rnum].Top = Top[ Book[i] ]; 
149             army[rnum].Rest = tim; 
150         }
151         else {
152             vis[now] = true; 
153         }
154     }
155     std::sort(army + 1, army + m + 1, Cmpmin); 
156     for (int i = 1; i <= m; i++) {
157         if (army[i].Rest < Tdis[ army[i].Top ]) {
158             if (!vis[ army[i].Top ] && Look(army[i].Top)) {
159                 vis[ army[i].Top ] = true; 
160                 army[i].Rest = -1; 
161             }
162         }
163     }
164     std::sort(army + 1, army + m + 1, Cmpmax); 
165     for (int i = Head[1]; i; i = e[i].next) {
166         int v = e[i].v; 
167         if (!vis[v] && Look(v)) {
168             q[++tail] = e[i].w; 
169         }
170     }
171     std::sort(q + 1, q + tail + 1, Cmp); 
172     for (int i = 1; i <= tail; i++) {
173         if (army[i].Rest < q[i]) {
174             return false;
175         }
176     }
177     return true; 
178 }
179 
180 int main(){
181     int u, v, w, R = 0, cnt1 = 0, Ans = 0; 
182     n = read(); 
183     
184     for (int i = 1; i < n; i++) {
185         u = read(); 
186         v = read(); 
187         w = read(); 
188         Add(u, v, w); 
189         R += w; 
190     }
191     dfs(1, 0); 
192     for (int i = Head[1]; i; i = e[i].next) {
193         int v = e[i].v; 
194         dfs1(v, 1, v, e[i].w); 
195     }
196     RMQ(); 
197     m = read(); 
198     for (int i = 1; i <= m; i++) {
199         Book[i] = read(); 
200     }
201     for (int i = Head[1]; i; i = e[i].next) {
202         cnt1++; 
203     }
204     if (cnt1 > m) {
205         printf("-1\n"); 
206         return 0; 
207     }
208     int L = 0; 
209     while (L <= R) {
210         int mid = (L + R) >> 1; 
211         if (judge(mid)) {
212             Ans = mid; 
213             R = mid - 1;
214         }
215         else {
216             L = mid + 1; 
217         }
218     }
219     printf("%d\n", Ans); 
220     return 0; 
221 } 

 


[树上倍增+二分答案][NOIP2012]运输计划

原文:https://www.cnblogs.com/GldHkkowo/p/9069077.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!