noip2013货车运输

发表于 | 分类于 |

noip2013货车运输

Description

给你一个由$n$个点，$m$条边组成的无向图，再给你$q$个询问，问你某两个点之间的所有路径中权值最小的边最大是多少？

若两点不连通则输出$-1$。

Input

第一行：两个整数$n,m$，表示点数和边数。

接下来$m$行：每行三个整数$a,b,c$，表示点$a$与点$b$之间有一条权值为$c$的边。

接下来一行：一个整数$q$，表示$q$个询问。

接下来$q$行：每行两个整数$a,b$，表示询问的两个点。

Output

$q$行，对应每组询问的答案。

Solution

要使路径中最小的边尽量大，做一遍最大生成树把不必要的边去掉，依照最大生成树的定义，我们可以知道在这棵树上两点之间的路径边权最小的边一定是最优的。

简化之后问题就是如何快速求树上两点之间的路径最小的边权。

直接算$lca$吧，在算$2^i$的祖先的同时可以顺便求一下某个点与它祖先之间的路径的最小边权。

最后对于询问的两点，就求$lca$，在求$lca$的同时也求路径上最小的边权。

Code

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#include<math.h>
#define INF 1e9
using namespace std;
const int maxn=10010;
const int maxm=50010;
struct TREE
{
	int u,v,d;
	TREE *last;
}tree[maxn*2];
TREE *root[maxn];
int tl=0;
void input(int u,int v,int d)
{
	tree[++tl].u=u;
	tree[tl].v=v;
	tree[tl].d=d;
	tree[tl].last=root[u];
	root[u]=&tree[tl];
}
struct Edge
{
	int u,v,d;
}edge[maxm];
bool cmp(Edge a,Edge b)
{
	return a.d>b.d;
}
int n,m,q;
int set[maxn];
int FH(int x)
{
	return set[x]==x?x:(set[x]=FH(set[x]));
}
void Kruskal()
{
	for(int i=1;i<=n;i++)
		set[i]=i;
	for(int i=1;i<=m;i++)
	{
		int u=edge[i].u,v=edge[i].v,d=edge[i].d;
		int fu=FH(u),fv=FH(v);
		if(fu!=fv)
		{
			input(u,v,d);
			input(v,u,d);
			set[fu]=fv;
		}
	}
}
int lca[maxn][30],deep[maxn],minD[maxn][30];
bool vis[maxn];
void LCA_dfs(int u,int fa)
{
	vis[u]=1;
	lca[u][1]=fa;
	deep[u]=deep[fa]+1;
	for(TREE *k=root[u];k!=NULL;k=k->last)
	{
		if(vis[k->v]) continue;
		LCA_dfs(k->v,u);
		minD[k->v][1]=k->d;
	}
}
void LCA()
{
	for(int i=1;i<=n;i++)
		if(!vis[i])
			LCA_dfs(i,0);
	for(int i=2;i<=20;i++)
		for(int j=1;j<=n;j++)
		{
			lca[j][i]=lca[lca[j][i-1]][i-1];
			minD[j][i]=min(minD[j][i-1],minD[lca[j][i-1]][i-1]);
		}
}
int findlca(int x,int y)
{
	int ans=INF;
	if(deep[x]<deep[y]) swap(x,y);
	
	for(int i=20;i>0;i--)
	{
		if(deep[lca[x][i]]<deep[y]) continue;
		ans=min(ans,minD[x][i]);
		x=lca[x][i];
	}
	if(x==y) return ans;
	for(int i=20;i>0;i--)
	{
		if(lca[x][i]==lca[y][i]) continue;
		ans=min(ans,min(minD[x][i],minD[y][i]));
		x=lca[x][i],y=lca[y][i];
	}
	ans=min(ans,min(minD[x][1],minD[y][1]));
	return ans;
}
void init()
{
	for(int i=0;i<maxn;i++)
		for(int j=0;j<30;j++) minD[i][j]=INF;
}
int main()
{
	scanf("%d%d",&n,&m);
	init();
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].d);
	
	sort(edge+1,edge+1+m,cmp);
	
	Kruskal();
	
	LCA();
	
	scanf("%d",&q);
	
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(FH(x)!=FH(y))
			printf("-1\n");
		else
			printf("%d\n",findlca(x,y));
	}
	return 0;
}