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:

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出样例#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.

题目分析

刚看到这个题目怎么也无法把它跟生成树联系到一起,直到后来看懂题是在求一条瓶颈路。
既然是两个点之间最小的边最大,那么很显然就是一条瓶颈路,求一条瓶颈路的方法有很多,有人应该会想到二分答案,这种方法是可行的,但是由于这道题是多次询问,时间难以承受,所以就要用生成树。上面博客已经介绍过这种方法,这里就不再赘述。由于是让路径上的最小边最大,所以应该拍一棵最大生成树,题中说的两点之间多条边也就对我们没什么影响。当生成一颗棵最大生成树后,任意两点之间的瓶颈路就是书上所保留下来的边组成的路,紧接着我们用倍增维护一下人任意点的祖先以及到该祖先路上的最小权值。然后就可以用LCA轻而易举的求出任意两点之间瓶颈路上的最小权值。对于输出-1的情况,一定是两个点不连通,可以用并查集来维护,然后这道题就可以AC啦!

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

# include <algorithm>
# include <cstring>
# include <iostream>
# include <cstdio>
# include <cmath>
# include <queue>
# define R register
# define LL long long

using namespace std;

struct pp {int v,u,w;} ed[50010];
struct bb {int v,w,pre;} edge[100010];
int f[10010][21],d[10010][21],dep[10010],fa[10010],h[10010],e,n,m,q;

inline void maxx(int &a,const int &b){a>b? :a=b;}

inline void in(R int &a){
R int c = getchar();R int x = 0,f = 1;
while(!isdigit(c)){if(c == '-')f=-1; c = getchar();}
while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
a = x*f;
}

inline void add(R int x,R int y,R int w){
edge[++e] = (bb){y,w,h[x]};
h[x] = e;
}

inline void minn(R int &x,const int y,const int z){x= y<z? y:z;}

inline bool cmp(pp a,pp b){return a.w>b.w;}

inline int find(R int x){return fa[x] = fa[x]==x? x:find(fa[x]);}

inline void dfs(R int x){

for(R int i=0; f[f[x][i]][i]; ++i) f[x][i+1] = f[f[x][i]][i],minn(d[x][i+1],d[x][i],d[f[x][i]][i]);

for(R int i=h[x]; i; i=edge[i].pre)
{
if(dep[edge[i].v]) continue;
f[edge[i].v][0] = x;
d[edge[i].v][0] = edge[i].w;
dep[edge[i].v] = dep[x]+1;
dfs(edge[i].v);
}
}

inline int lca(R int x,R int y){
R int ans = 2147483647;
if(dep[x]<dep[y]) x^=y,y^=x,x^=y;
R int t = log2(dep[x]-dep[y])+1;
for(R int i=t; i>=0; --i) if(dep[f[x][i]] >= dep[y]) minn(ans,ans,d[x][i]),x = f[x][i];
if(x == y) return ans;
t = log2(dep[x])+1;
for(R int i=t; i>=0; --i)
{

if(f[x][i] == f[y][i]) continue;
R int tot;
minn(tot,d[x][i],d[y][i]);
x=f[x][i],y=f[y][i];
minn(ans,ans,tot);
}
R int tot;
minn(tot,d[x][0],d[y][0]);
minn(ans,ans,tot);
return ans;
}

inline int yg(){
freopen("truck.in","r",stdin);
freopen("truck.out","w",stdout);
in(n),in(m);
R int x,y,z;
for(R int i=1; i<=n; ++i) fa[i] = i;
for(R int i=1; i<=m; ++i)
{
in(x),in(y),in(z);
ed[i]=(pp){x,y,z};
}
sort(ed+1,ed+m+1,cmp);
for(R int i=1; i<=m; ++i)
{
R int p=find(ed[i].u),q=find(ed[i].v);
if(p!=q) add(ed[i].u,ed[i].v,ed[i].w),add(ed[i].v,ed[i].u,ed[i].w),fa[p] = q;
}
dep[1] = 1;
dfs(1);
in(q);
for(R int i=1; i<=q; ++i)
{
in(x),in(y);
if(find(x)!=find(y)) {printf("-1\n");continue;}
printf("%d\n",lca(x,y));
}
}

int youngsc = yg();
int main(){;}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 题目描述
  2. 2. 输入输出格式
    1. 2.1. 输入格式:
    2. 2.2. 输出格式:
    3. 2.3. 输入输出样例
  3. 3. 输入样例#1:
  4. 4. 输出样例#1:
  5. 5. 说明
  6. 6. 题目分析
  7. 7. 代码如下
,