首页 > 其他 > 详细

NOIP2015 运输计划

时间:2018-02-14 23:14:39      阅读:102      评论:0      收藏:0      [点我收藏+]

标签:输入格式   log   ++   body   bad   span   printf   ora   物流   

题目背景

公元 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的物流公司完成阶段性工作所需要的最短时间。

输入输出样例

输入样例#1: 复制
6 3 
1 2 3 
1 6 4 
3 1 7 
4 3 6 
3 5 5 
3 6 
2 5 
4 5
输出样例#1: 复制
11

说明

所有测试数据的范围和特点如下表所示

技术分享图片

请注意常数因子带来的程序效率上的影响。

气死我了调了一晚上就是因为dif数组忘记清零

 

  1 //2018年2月14日19:17:34 
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 const int N = 3000001;
  8 const int M = 3000001;
  9 int n, m;
 10 int x[N], y[N], LCA[N];
 11 int fir[N], edge_Num, nxt[M], to[M], w[M];
 12 int dis[N], ans;
 13 void addEdge(int x, int y, int z){
 14     to[++edge_Num] = y;
 15     w[edge_Num] = z;
 16     nxt[edge_Num] = fir[x];
 17     
 18     fir[x] = edge_Num;
 19 }
 20 
 21 int p[N][23], deep[N], len[N];
 22 void dfs(int u){
 23     for(int i=1;i<=22;i++){
 24         if(deep[u] < (1<<i)) break;
 25         p[u][i] = p[p[u][i-1]][i-1];
 26     }
 27     for(int i=fir[u]; i; i=nxt[i])
 28         if(!deep[to[i]]){
 29             len[to[i]] = len[u] + w[i];
 30             deep[to[i]] = deep[u] + 1;
 31             p[to[i]][0] = u;
 32             dfs(to[i]);
 33         }
 34 }
 35 
 36 int lca(int u, int v){
 37     if(deep[u] < deep[v]) swap(u, v);
 38     int c = deep[u] - deep[v];
 39     for(int i=0;i<=22;i++)
 40         if((1<<i) & c)
 41             u = p[u][i];
 42     if(u == v) return u;
 43     for(int i=22;i>=0;i--)
 44         if(p[u][i] != p[v][i]){
 45             u = p[u][i];
 46             v = p[v][i];
 47         }
 48     return p[u][0];
 49 }
 50 int dif[N];
 51 void ddd(int x, int fa){
 52     for(int i=fir[x]; i; i=nxt[i]){
 53         if(to[i] != fa){
 54             ddd(to[i], x);
 55             dif[x] += dif[to[i]];
 56         }
 57     }
 58 }
 59 bool check(int mi){
 60     int num = 0;
 61     int mx = 0;
 62     memset(dif, 0, sizeof(dif)); //毒瘤啊, 一定不要忘记清零!!!!!! 
 63     for(int i=1;i<=m;i++){
 64         if(mi < dis[i]){
 65             num++;
 66             dif[x[i]]++;
 67             dif[y[i]]++;
 68             dif[LCA[i]] -= 2;
 69             mx = max(dis[i], mx);
 70         }
 71     }
 72     ddd(1, 1);
 73     for(int i=1; i<=n; i++){
 74         int fa = p[i][0];
 75         for(int j=fir[fa]; j; j=nxt[j])
 76             if(to[j] == i){
 77                 if(num == dif[i] && mx-w[j] <= mi)
 78                 return true;
 79             }
 80     }
 81     return false;
 82 }
 83 
 84 int l, r;
 85 
 86 int main(){
 87     scanf("%d%d", &n, &m);
 88     for(int i=1;i<n;i++){
 89         int x, y, z;
 90         scanf("%d%d%d", &x, &y, &z);
 91         addEdge(x, y, z);
 92         addEdge(y, x, z);
 93     }
 94     p[1][0] = 1;
 95     deep[1] = 1;
 96     dfs(1);
 97     for(int i=1;i<=m;i++){
 98         scanf("%d%d", &x[i], &y[i]);
 99         LCA[i] = lca(x[i], y[i]);
100         dis[i] = len[x[i]] + len[y[i]] - 2*len[LCA[i]];
101         r = max(r, dis[i]);
102     }
103     l = 1;
104     while(l <= r){
105         int mid = (l + r) >> 1;
106         if(check(mid)) r = mid-1, ans = mid;
107         else l = mid+1;
108     }
109     printf("%d\n", ans);
110 
111     return 0;
112 }

 

 

 

NOIP2015 运输计划

标签:输入格式   log   ++   body   bad   span   printf   ora   物流   

原文:https://www.cnblogs.com/sineagle/p/8449060.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号