[NOIP2013] 货车运输

题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道

路。接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式：

输出文件名为 truck.out。

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货

车不能到达目的地，输出-1。

输入输出样例

输入样例#1：

输出样例#1：

3
-1
3

说明

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；

对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；

对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。

题解：

最大生出树+树链剖分

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<stack>
  9 #include<queue>
 10 #include<map>
 11 #define RG register
 12 #define IL inline
 13 #define pi acos(-1.0)
 14 #define ll long long
 15 #define ls x<<1
 16 #define rs x<<1|1
 17 #define MID int mid=(l+r)>>1;
 18 #define inf 1<<30
 19 using namespace std;
 20 
 21 const int maxn = 10010;
 22 const int maxm = 50010;
 23 
 24 int gi() {
 25   char ch=getchar(); int x=0;
 26   while(ch<'0' || ch>'9') ch=getchar();
 27   while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}
 28   return x;
 29 }
 30 
 31 int n,m,k,z,q,fa[maxm];
 32 int nxt[maxm*2],to[maxm*2],dis[maxm*2],h[maxn],e_num;
 33 int siz[maxn],son[maxn],top[maxn],dep[maxn],fat[maxn],w[maxn],dfn[maxn],rev[maxn];
 34 int tr[maxn*4];
 35 bool bj[maxn];
 36 struct EDGE {
 37   int x,y,v;
 38 }e[maxm],E[maxm];
 39 
 40 bool cmp(EDGE a, EDGE b) {
 41   return a.v>b.v;
 42 }
 43 
 44 int find(int x) {
 45   if(fa[x]!=x) fa[x]=find(fa[x]);
 46   return fa[x];
 47 }
 48 
 49 void add(int x, int y, int v) {
 50   nxt[++e_num]=h[x];
 51   to[e_num]=y;
 52   dis[e_num]=v;
 53   h[x]=e_num;
 54 }
 55 
 56 void dfs1(int u) {
 57   siz[u]=1;
 58   for(int i=h[u]; i; i=nxt[i]) {
 59     int v=to[i];
 60     if(v==fat[u]) continue;
 61     fat[v]=u;
 62     dep[v]=dep[u]+1;
 63     w[v]=dis[i];
 64     dfs1(v);
 65     if(siz[v]>siz[son[u]]) son[u]=v;
 66     siz[u]+=siz[v];
 67   }
 68 }
 69 
 70 void dfs2(int u) {
 71   dfn[u]=++z;rev[z]=u;
 72   if(son[u]) top[son[u]]=top[u],dfs2(son[u]);
 73   for(int i=h[u]; i; i=nxt[i]) {
 74     int v=to[i];
 75     if(v==fat[u] || v==son[u]) continue;
 76     top[v]=v,dfs2(v);
 77   }
 78 }
 79 
 80 void build(int x, int l, int r) {
 81   if(l==r) {tr[x]=w[rev[l]];return;}
 82   MID;
 83   build(ls,l,mid),build(rs,mid+1,r);
 84   tr[x]=min(tr[ls],tr[rs]);
 85 }
 86 
 87 int query(int x, int l, int r, int ql, int qr) {
 88   if(l>=ql && r<=qr) return tr[x];
 89   MID;
 90   if(qr<=mid) return query(ls,l,mid,ql,qr);
 91   else if(ql>mid) return query(rs,mid+1,r,ql,qr);
 92   return min(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
 93 }
 94 
 95 int lca(int x, int y) {
 96   int tmp=inf;
 97   while(top[x]!=top[y]) {
 98     if(dep[top[x]]>dep[top[y]]) tmp=min(tmp,query(1,1,z,dfn[top[x]],dfn[x])),x=fat[top[x]];
 99     else tmp=min(tmp,query(1,1,z,dfn[top[y]],dfn[y])),y=fat[top[y]];
100   }
101   if(x==y) return tmp;
102   else {
103     if(dep[x]>dep[y]) swap(x,y);
104     tmp=min(tmp,query(1,1,z,dfn[x]+1,dfn[y]));
105   }
106   return tmp;
107 }
108 
109 int main() {
110   n=gi(),m=gi();
111   for(int i=1; i<=m; i++) {
112     E[i].x=gi(),E[i].y=gi(),E[i].v=gi();
113     fa[i]=i;
114   }
115   sort(E+1,E+m+1,cmp);
116   for(int i=1; i<=m; i++) {
117     int x=find(E[i].x),y=find(E[i].y);
118     if(x==y) continue;
119     e[++k].x=E[i].x,e[k].y=E[i].y,e[k].v=E[i].v;
120     fa[y]=x;
121     if(k==n-1) break;
122   }
123   for(int i=1; i<=k; i++) {
124     bj[e[i].x]=1,bj[e[i].y]=1;
125     add(e[i].x,e[i].y,e[i].v);
126     add(e[i].y,e[i].x,e[i].v);
127   }
128   dep[1]=1,fat[1]=1,top[1]=1,w[1]=inf;
129   dfs1(1),dfs2(1),build(1,1,z);
130   q=gi();
131   for(int i=1; i<=q; i++) {
132     int x=gi(),y=gi();
133     if(!bj[x] || !bj[y]) printf("-1
");
134     else printf("%d
", lca(x,y));
135   }
136 }

总结——图上最小（大）边的最大（小）化问题

1、路径上最小边的最大值：最大生成树+树链最小值

2、路径上最大边的最小值：最小生成树+树链最大值