NOIP2015-D2T3运输计划

题目背景

公元 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：

输出样例#1：

说明

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

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

这题首先用的是二分+暴力判断

二分答案然后把大于m的树链一一枚举，找可行的边取交集

80分

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<algorithm>
  4 #include<cstring>
  5 #define MAXN 300005
  6 #define LOG 20
  7 #define pii pair<int,int>
  8 using namespace std;
  9 int first[MAXN],Next[MAXN*2],to[MAXN*2],W[MAXN*2],cnt;
 10 int n,m;
 11 int fa[LOG][MAXN],d[LOG][MAXN],dep[MAXN];
 12 int mid;
 13 struct Lian{
 14     int x,y,lca;
 15     int Val;
 16     friend bool operator < (const Lian &p1,const Lian &p2){
 17         return (p1.Val<p2.Val);
 18     }
 19     friend bool operator > (const Lian &p1,const Lian &p2){
 20         return !(p1.Val<p2.Val);
 21     }
 22 } s[MAXN];
 23 void Add(int x,int y,int w){
 24     Next[++cnt]=first[x]; first[x]=cnt; to[cnt]=y; W[cnt]=w;
 25     Next[++cnt]=first[y]; first[y]=cnt; to[cnt]=x; W[cnt]=w;
 26     // double edge
 27 }
 28 void dfs(int x){
 29     for(int e=first[x];e;e=Next[e]){
 30         int y=to[e],w=W[e];
 31         if(y==fa[0][x]){
 32             continue;
 33         }
 34         fa[0][y]=x;
 35         d[0][y]=w;
 36         dep[y]=dep[x]+1;
 37         dfs(y);
 38     }
 39 }
 40 pii LCA(int x,int y){
 41     if(dep[x]<dep[y]){
 42         swap(x,y);
 43     }
 44     int L=0;
 45     for(int k=dep[x]-dep[y],p=0;k;k>>=1,p++){
 46         if(k&1){
 47             L+=d[p][x];
 48             x=fa[p][x];
 49         }
 50     }
 51     if(x==y){
 52         return make_pair(L,x);
 53     }
 54     for(int k=LOG-1;k>=0;k--){
 55         if(fa[k][x]!=fa[k][y]){
 56             L+=d[k][x];
 57             L+=d[k][y];
 58             x=fa[k][x];
 59             y=fa[k][y];
 60         }
 61     }
 62     return make_pair(L+d[0][x]+d[0][y],fa[0][x]);
 63 }
 64 int b[MAXN];
 65 bool check(){
 66     memset(b,0,sizeof(b));
 67     Lian t;t.Val=mid;
 68     int Pos=upper_bound(s+1,s+m+1,t)-s;
 69     if(Pos>m){
 70         return 1;
 71     }
 72     int num=m-Pos+1;
 73     for(int i=Pos;i<=m;i++){
 74         int lc=s[i].x,rc=s[i].y;
 75         int lca=s[i].lca,L=s[i].Val;
 76         while(lc!=lca){
 77             if(L-d[0][lc]<=mid){
 78                 b[lc]++;
 79                 if(b[lc]>=num){
 80                     return 1;
 81                 }
 82             }
 83             lc=fa[0][lc];
 84         }
 85         while(rc!=lca){
 86             if(L-d[0][rc]<=mid){
 87                 b[rc]++;
 88                 if(b[rc]>=num){
 89                     return 1;
 90                 }
 91             }
 92             rc=fa[0][rc];
 93         }
 94     }
 95     return 0;
 96 }
 97 int main()
 98 {
 99 //    freopen("T1.in","r",stdin);
100 //    freopen("my.out","w",stdout);
101     scanf("%d%d",&n,&m);
102     for(int i=1;i<n;i++){
103         int x,y,w;
104         scanf("%d%d%d",&x,&y,&w);
105         Add(x,y,w);
106     }
107     dep[1]=1;
108     dfs(1);
109     for(int k=1;k<LOG;k++){
110         for(int i=1;i<=n;i++){
111             fa[k][i]=fa[k-1][fa[k-1][i]];
112             d[k][i]=d[k-1][i]+d[k-1][fa[k-1][i]];
113         }
114     }
115     for(int i=1;i<=m;i++){
116         scanf("%d%d",&s[i].x,&s[i].y);
117         pii t=LCA(s[i].x,s[i].y);
118         s[i].lca=t.second;
119         s[i].Val=t.first;
120     }
121     sort(s+1,s+m+1);
122 //    for(int i=1;i<=n;i++){
123 //        mid=s[i].Val;
124 //        if(check()){
125 //            printf("1
");
126 //        }
127 //        else{
128 //            printf("0
");
129 //        }
130 //    }
131     int L=1,R=s[m].Val;
132     while(L<R-1){
133         mid=(L+R)/2;
134         if(check()){
135             R=mid;
136         }
137         else{
138             L=mid;
139         }
140     }
141     mid=L; if(check()){
142         printf("%d
",L);
143     }
144     else{
145         printf("%d
",R);
146     }
147     return 0;
148 }

View Code

实际上判断用树上差分提高效率即可AC

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<algorithm>
  4 #include<cstring>
  5 #define MAXN 300005
  6 #define LOG 20
  7 #define pii pair<int,int>
  8 using namespace std;
  9 int first[MAXN],Next[MAXN*2],to[MAXN*2],W[MAXN*2],cnt;
 10 int n,m;
 11 int fa[LOG][MAXN],d[LOG][MAXN],dep[MAXN];
 12 int mid;
 13 struct Lian{
 14     int x,y,lca;
 15     int Val;
 16     friend bool operator < (const Lian &p1,const Lian &p2){
 17         return (p1.Val<p2.Val);
 18     }
 19     friend bool operator > (const Lian &p1,const Lian &p2){
 20         return !(p1.Val<p2.Val);
 21     }
 22 } s[MAXN];
 23 void Add(int x,int y,int w){
 24     Next[++cnt]=first[x]; first[x]=cnt; to[cnt]=y; W[cnt]=w;
 25     Next[++cnt]=first[y]; first[y]=cnt; to[cnt]=x; W[cnt]=w;
 26     // double edge
 27 }
 28 void dfs(int x){
 29     for(int e=first[x];e;e=Next[e]){
 30         int y=to[e],w=W[e];
 31         if(y==fa[0][x]){
 32             continue;
 33         }
 34         fa[0][y]=x;
 35         d[0][y]=w;
 36         dep[y]=dep[x]+1;
 37         dfs(y);
 38     }
 39 }
 40 pii LCA(int x,int y){
 41     if(dep[x]<dep[y]){
 42         swap(x,y);
 43     }
 44     int L=0;
 45     for(int k=dep[x]-dep[y],p=0;k;k>>=1,p++){
 46         if(k&1){
 47             L+=d[p][x];
 48             x=fa[p][x];
 49         }
 50     }
 51     if(x==y){
 52         return make_pair(L,x);
 53     }
 54     for(int k=LOG-1;k>=0;k--){
 55         if(fa[k][x]!=fa[k][y]){
 56             L+=d[k][x];
 57             L+=d[k][y];
 58             x=fa[k][x];
 59             y=fa[k][y];
 60         }
 61     }
 62     return make_pair(L+d[0][x]+d[0][y],fa[0][x]);
 63 }
 64 int b[MAXN];
 65 int num;
 66 int find(int x){
 67     int ret=0;
 68     for(int e=first[x];e;e=Next[e]){
 69         int y=to[e];
 70         if(y==fa[0][x]) continue;
 71         ret=max(ret,find(y));
 72         b[x]+=b[y];
 73     }
 74     if(b[x]==num){
 75         ret=max(ret,d[0][x]);
 76     }
 77     return ret;
 78 }
 79 bool check(){
 80     memset(b,0,sizeof(b));
 81     Lian t;t.Val=mid;
 82     int Pos=upper_bound(s+1,s+m+1,t)-s;
 83     if(Pos>m){
 84         return 1;
 85     }
 86     num=m-Pos+1;
 87     for(int i=Pos;i<=m;i++){
 88         int lc=s[i].x,rc=s[i].y;
 89         int lca=s[i].lca,L=s[i].Val;
 90         b[lc]++,b[rc]++;
 91         b[lca]-=2;
 92     }
 93     int temp=find(1);
 94     return (s[m].Val-temp<=mid);
 95 }
 96 int main()
 97 {
 98  //   freopen("T1.in","r",stdin);
 99 //    freopen("my.out","w",stdout);
100     scanf("%d%d",&n,&m);
101     for(int i=1;i<n;i++){
102         int x,y,w;
103         scanf("%d%d%d",&x,&y,&w);
104         Add(x,y,w);
105     }
106     dep[1]=1;
107     dfs(1);
108     for(int k=1;k<LOG;k++){
109         for(int i=1;i<=n;i++){
110             fa[k][i]=fa[k-1][fa[k-1][i]];
111             d[k][i]=d[k-1][i]+d[k-1][fa[k-1][i]];
112         }
113     }
114     for(int i=1;i<=m;i++){
115         scanf("%d%d",&s[i].x,&s[i].y);
116         pii t=LCA(s[i].x,s[i].y);
117         s[i].lca=t.second;
118         s[i].Val=t.first;
119     }
120     sort(s+1,s+m+1);
121 //    for(int i=1;i<=n;i++){
122 //        mid=s[i].Val;
123 //        if(check()){
124 //            printf("1
");
125 //        }
126 //        else{
127 //            printf("0
");
128 //        }
129 //    }
130     int L=0,R=s[m].Val;
131     while(L<R-1){
132         mid=(L+R)/2;
133         if(check()){
134             R=mid;
135         }
136         else{
137             L=mid;
138         }
139     }
140     mid=L; if(check()){
141         printf("%d
",L);
142     }
143     else{
144         printf("%d
",R);
145     }
146     return 0;
147 }

View Code