P1967 货车运输

题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 q* 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 n,m，表示 A 国有 n 座城市和 m 条道路。

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

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

接下来 q 行，每行两个整数 x,y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，保证 x\=y

输出格式

共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 −1。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出 #1

1
2
3
3
-1
3

先求最大生成树，将生成树转为有根树，然后跑 lca (buhui)

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
const int INF=0x3f3f3f3f;
const int MAX=10000+10;
int n,m,f[MAX],x,y,z,q,vis[MAX];
int fa[MAX],l[MAX],cost[MAX]; //fa 父节点; l 节点深度; cost 节点到父节点的距离;
int anc[MAX][25],val[MAX][25];//anc(i,j) 节点i的第2^j级祖先编号
							  //maxcost(i,j)  节点i的第2^j级组先之间路径上的最大权值 
int find(int x){
	return f[x]==-1?x:f[x]=find(f[x]);
}
struct edge{
	int x,y,c;
	bool operator< (const edge&x)const{
		return c>x.c;
	}
}e[MAX*5];
struct edge2{
	int to,next,c;
}ve[MAX*2];
int head[MAX],tot=0;
void addedge(int u,int v,int c){
	ve[tot].to=v;
	ve[tot].c=c;
	ve[tot].next=head[u];
	head[u]=tot++;
}
void dfs(int u){ //转有根树 
	vis[u]=1;
	for(int i=head[u];i!=-1;i=ve[i].next){
		int v=ve[i].to;
		if(vis[v]) continue;
		l[v]=l[u]+1;
		fa[v]=u;
		cost[v]=ve[i].c;
		dfs(v);
	}
}
void pre(){
	mem(val,0x3f);
	fi(i,1,n+1){
		anc[i][0]=fa[i];val[i][0]=cost[i];
		for(int j=1;j<=20;j++)anc[i][j]=-1;//表示祖先不存在 
	}
	for(int j=1;j<=20;j++) //预处理出节点 i 的第2^j级祖先编号 和 路径上的最大权值
		fi(i,1,n+1)
			if(anc[i][j-1]!=-1){
				int a=anc[i][j-1];
				anc[i][j]=anc[a][j-1];
				val[i][j]=min(val[i][j-1],val[a][j-1]);
			}
}
int lca(int p,int q){
	if(find(p)!=find(q))return -1;
	if(l[p]<l[q]) swap(p,q);
	int ans=INF;
	for(int i=20;i>=0;i--)     //使 p,q 深度相等
		if(l[anc[p][i]]>=l[q]){
			ans = min(ans,val[p][i]);
			p=anc[p][i];
		}
	if(p==q) return ans;//lca 为 p
	for(int i=20;i>=0;i--)     //向上找共同的祖先节点
		if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
			ans = min(ans,min(val[p][i],val[q][i]));
			p=anc[p][i];q=anc[q][i];
		}
	return min(ans,min(val[p][0],val[q][0]));//
}
int main(){
	freopen("in","r",stdin);
	mem(f,-1);mem(fa,-1);mem(head,-1);
	sf(n);sf(m);
	fi(i,0,m){
		sf(e[i].x);sf(e[i].y);sf(e[i].c);
	}
	sort(e,e+m);
	fi(i,0,m){
		int u = find(e[i].x);
		int v = find(e[i].y);
		if(u!=v){
			f[u]=v;
			addedge(e[i].x,e[i].y,e[i].c);
			addedge(e[i].y,e[i].x,e[i].c);
		}
	}
	fa[1]=-1;
	fi(i,1,n+1)
		if(!vis[i]){ // 处理森林
			l[i]=1;
			dfs(i);
			pre();
		}
	sf(q);
	while(q--){
		sf(x);sf(y);
		pf(lca(x,y));pfc("\n");
	}
	return 0;
}