cogs 2109. [NOIP2015] 运输计划 WD

★★★ 输入文件：transport.in 输出文件：transport.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

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

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

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物

流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。

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

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

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

【输入格式】

第一行包括两个正整数 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 的物流公司完成阶段性工作所需要的最短时间。

【样例输入】

【样例输出】

【提示】

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

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

15年noip的题简单（错误）思路：spfa+path（稳稳的超时）：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<cstring>
  6 #include<string>
  7 #include<queue>
  8 
  9 using namespace std;
 10 const int N=300010;
 11 const int maxn=99999;
 12 
 13 int n;
 14 int m;
 15 int now=1;
 16 int dis[N];
 17 int head[N];
 18 int path[N];
 19 bool vis[N];
 20 int bian[N];
 21 int total;
 22 queue<int>q;
 23 
 24 struct node {
 25     int u,v,w,nxt;
 26     int js;
 27 }E[N];
 28 
 29 struct NODE {
 30     int start;
 31     int end;
 32     int Answer;
 33 }Ask[N];
 34 
 35 inline void Add(int u,int v,int w)
 36 {
 37     E[now].u=u;
 38     E[now].v=v;
 39     E[now].w=w;
 40     E[now].js=now;
 41     E[now].nxt=head[u];
 42     head[u]=now;
 43     now++;
 44 }
 45 
 46 inline int read()
 47 {
 48     int x=0,f=1;
 49     char c=getchar();
 50     while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); }
 51     while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
 52     return x*f;
 53 }
 54 
 55 inline void JB(int ST,int EN)
 56 {
 57     int start=ST;
 58     int end=EN;
 59     
 60     while(end!=ST)
 61     {
 62         bian[path[end]]++;
 63         end=E[path[end]].u;
 64     }
 65 }
 66 
 67 inline void chu()
 68 {
 69     for(int i=1;i<=n;i++)
 70         vis[i]=0,dis[i]=maxn,path[i]=0;
 71     while(!q.empty())q.pop();
 72 }
 73 
 74 inline void spfa(int start,int end,int x)
 75 {
 76     chu();
 77     vis[start]=1;
 78     dis[start]=0;
 79     q.push(start);
 80     
 81     while(!q.empty())
 82     {
 83         int top=q.front();
 84         q.pop();
 85         vis[top]=0;
 86         
 87         for(int i=head[top];i!=-1;i=E[i].nxt)
 88         {
 89             if(dis[E[i].v]>dis[E[i].u]+E[i].w)
 90             {
 91                 dis[E[i].v]=dis[E[i].u]+E[i].w;
 92                 path[E[i].v]=E[i].js;
 93                 if(!vis[E[i].v]) q.push(E[i].v);
 94             }
 95         }
 96     }
 97     JB(start,end);
 98     Ask[x].Answer=dis[end];
 99 }
100 
101 inline bool cmp(NODE a,NODE b)
102 {
103     return a.Answer>b.Answer;
104 }
105 
106 int main()
107 {
108     n=read();
109     m=read();
110     
111     for(int i=1;i<=n;i++)
112         head[i]=-1;
113     
114     for(int i=1;i<=n-1;i++)
115     {
116         int u,v,w;
117         u=read();
118         v=read();
119         w=read();
120         Add(u,v,w);
121     }
122     for(int i=1;i<=m;i++)
123     {
124         int start,end;
125         Ask[i].start=read();
126         Ask[i].end=read();
127         spfa(Ask[i].start,Ask[i].end,i);
128     }
129     
130     sort(bian+1,bian+n+1);
131     int YJ=0;
132     for(int i=n;i>=1;i--)
133     {
134         if(bian[i]==m&&E[i].w>E[YJ].w)
135             YJ=i;
136     }
137     
138     sort(Ask,Ask+m+1,cmp);
139     printf("%d",Ask[1].Answer-E[YJ].w);
140     
141     return 0;
142 }

lca+dfs：

  1 #include<set>
  2 #include<queue>
  3 #include<vector>
  4 #include<cstdio>
  5 #include<cstring>
  6 #include<algorithm>
  7 
  8 using namespace std;
  9 const int maxn=300005;
 10 
 11 int n,m;
 12 set<int> s1;
 13 set<int> s2;
 14 set<int>::iterator It;
 15 vector<int> G[maxn];
 16 
 17 struct Edge {
 18     int from,to,cap;
 19 };
 20 struct Heapnode {
 21     int id,len;
 22 };
 23 bool operator <(const Heapnode &a,const Heapnode &b) {
 24     return a.len<b.len;
 25 }
 26 bool operator >(const Heapnode &a,const Heapnode &b) {
 27     return a.len>b.len;
 28 }
 29 priority_queue<Heapnode> heap;
 30 struct Query {
 31     int u,v,len,lca;
 32     bool operator < (const Query& rhs) const {
 33         return len>rhs.len;
 34     }
 35 };
 36 Query Q[maxn];
 37 vector<Edge> edges;
 38 int f[maxn][20],dist[maxn],d[maxn],num[maxn];
 39 int readint() {
 40     int x=0;
 41     char ch=getchar();
 42     while(ch<'0'||ch>'9') ch=getchar();
 43     while(ch>='0'&&ch<='9') {
 44         x=x*10+ch-'0';
 45         ch=getchar();
 46     }
 47     return x;
 48 }
 49 void dfs(int u,int fa,int sum) {
 50     dist[u]=sum;
 51     d[u]=d[fa]+1;
 52     f[u][0]=fa;
 53     for(int i=1; i<20; i++)
 54         f[u][i]=f[f[u][i-1]][i-1];
 55     for(int i=0; i<G[u].size(); i++) {
 56         if(edges[G[u][i]].to!=fa) dfs(edges[G[u][i]].to,u,sum+edges[G[u][i]].cap);
 57         else num[u]=G[u][i];
 58     }
 59 }
 60 void Lca1(int &u,int &v,int cnt) {
 61     int su=u,sv=v;
 62     if(d[u]>d[v]) {
 63         u^=v;
 64         v^=u;
 65         u^=v;
 66     }
 67     int dis=d[v]-d[u];
 68     int ret=dist[v]+dist[u];
 69     for(int i=19; i>=0; i--) {
 70         if((dis>>i)&1) v=f[v][i];
 71     }
 72     for(int i=19; i>=0; i--) {
 73         if(f[u][i]!=f[v][i]) {
 74             u=f[u][i];
 75             v=f[v][i];
 76         }
 77     }
 78     if(u!=v) {
 79         u=f[u][0];
 80         v=f[v][0];
 81     }
 82     ret-=2*dist[u];
 83     Q[cnt].u=su;
 84     Q[cnt].v=sv;
 85     Q[cnt].len=ret;
 86     Q[cnt].lca=u;
 87 }
 88 void Add_Edge1(int u,int k) {
 89     if(u==Q[k].lca) return;
 90     s1.insert(num[u]);
 91     heap.push((Heapnode) {
 92         num[u],edges[num[u]].cap
 93     });
 94     Add_Edge1(edges[num[u]].to,k);
 95 }
 96 void Add_Edge(int u,int k) {
 97     if(u==Q[k].lca) return;
 98     s2.insert(num[u]);
 99     Add_Edge(edges[num[u]].to,k);
100 }
101 int main() {
102     freopen("transport.in","r",stdin);
103     freopen("transport.out","w",stdout);
104     n=readint();
105     m=readint();
106     int from,to,cap;
107     for(int i=1; i<n; i++) {
108         from=readint();
109         to=readint();
110         cap=readint();
111         edges.push_back((Edge) {
112             from,to,cap
113         });
114         edges.push_back((Edge) {
115             to,from,cap
116         });
117         G[from].push_back(edges.size()-2);
118         G[to].push_back(edges.size()-1);
119     }
120     dfs(1,0,0);
121     int u,v,len;
122     for(int i=0; i<m; i++) {
123         u=readint();
124         v=readint();
125         Lca1(u,v,i);
126     }
127     sort(Q,Q+m);
128     int ans=0;
129     s1.clear();
130     s2.clear();
131     Add_Edge1(Q[0].u,0);
132     Add_Edge1(Q[0].v,0);
133     ans=Q[0].len-(heap.top()).len;
134     for(int i=1; i<m; i++) {
135         if(ans>=Q[i].len) break;
136         ans=Q[i].len;
137         Add_Edge(Q[i].u,i);
138         Add_Edge(Q[i].v,i);
139         It=s1.begin();
140         for(It; It!=s1.end();) {
141             int cnt=(*It);
142             It++;
143             if(!s2.count(cnt)) {
144                 s1.erase(cnt);
145             }
146         }
147         s2.clear();
148         if(s1.empty()) break;
149         while(!s1.count(heap.top().id)) {
150             heap.pop();
151         }
152         if(Q[0].len-(heap.top()).len>=ans) break;
153         ans=Q[0].len-(heap.top()).len;
154     }
155     printf("%d",ans);
156     return 0;
157 }