【ybt高效進階4-5-4】【luogu P1967】貨車運輸

貨車運輸

題目連結：ybt高效進階4-5-4 / luogu P1967

題目大意

有一些點，然後又一些有權值的邊。

然後多組詢問，每次給你兩個點，要你找一條路徑，使得這條路徑上權值最小的邊的權值最大。（輸出權值）

如果沒有路徑就輸出 -1。

思路

那首先我們看到它是找路徑，然後路徑不是權值相加，而是權值的極值。

自然想到貪心弄一個最大生成樹的東西。

那就由圖變成了樹，然後要找的就變成了樹上的路徑。

那我們可以考慮用 LCA 來搞數的路徑。

然後預處理跳的父親的時候同時也可以把這麼跳經過的路徑的最大權值。

然後兩個點的詢問就變成了跳 LCA，然後在跳的時候把每次跳的那一段的最小權值取一個最小值，就是答案了。

判斷是否有路徑其實就是判斷是否連通，那我們可以用最大生成樹的并查集來判斷。

代碼

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

struct road {
	int x, y, z;
}ee[50001];
struct node {
	int x, to, nxt;
}e[100001];
int n, m, nn, q;
int fa[10001], x, y;
int le[10001], KK, ans;
int f[21][10001], deg[10001], dis[21][10001];

bool cmp(road x, road y) {
	return x.z > y.z;
}

int find(int now) {//并查集
	if (fa[now] == now) return now;
	return fa[now] = find(fa[now]);
}

void connect(int x, int y) {
	int X = find(x), Y = find(y);
	fa[X] = Y;
}

void add(int x, int y, int z) {//建樹
	e[++KK] = (node){z, y, le[x]}; le[x] = KK;
	e[++KK] = (node){z, x, le[y]}; le[y] = KK;
}

void dfs(int now, int father) {
	deg[now] = deg[father] + 1;
	f[0][now] = father;
	for (int i = le[now]; i; i = e[i].nxt)
		if (e[i].to != father) {
			dis[0][e[i].to] = e[i].x;
			dfs(e[i].to, now);
		}
}

int LCA(int x, int y) {
	if (deg[y] > deg[x]) swap(x, y);
	
	for (int i = 20; i >= 0; i--)
		if (deg[f[i][x]] >= deg[y]) {
			ans = min(ans, dis[i][x]);
			x = f[i][x];
		}
	if (x == y) return x;
	
	for (int i = 20; i >= 0; i--)
		if (f[i][x] != f[i][y]) {
			ans = min(ans, dis[i][x]);
			ans = min(ans, dis[i][y]);
			x = f[i][x];
			y = f[i][y];
		}
	
	ans = min(ans, dis[0][x]);
	ans = min(ans, dis[0][y]);
	return f[0][x];
}

int main() {
	memset(dis, 0x7f, sizeof(dis));
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++)
		scanf("%d %d %d", &ee[i].x, &ee[i].y, &ee[i].z);
	
	sort(ee + 1, ee + m + 1, cmp);
	
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) {//最大生成樹
		int x = find(ee[i].x), y = find(ee[i].y);
		if (x == y) continue;
		
		nn++;
		connect(ee[i].x, ee[i].y);
		add(ee[i].x, ee[i].y, ee[i].z);
		
		if (nn == n - 1) break;
	}
	
	dfs(1, 0);//把弄出的樹進行倍增
	for (int i = 1; i <= 20; i++)
		for (int j = 1; j <= n; j++) {
			f[i][j] = f[i - 1][f[i - 1][j]];
			dis[i][j] = min(dis[i - 1][j], dis[i - 1][f[i - 1][j]]);
		}
	
	scanf("%d", &q);
	while (q--) {
		scanf("%d %d", &x, &y);
		
		if (find(x) != find(y)) {
			printf("-1\n");
			continue;
		}
		
		ans = 1e9;
		LCA(x, y);//在跳LCA的過程中統計答案
		printf("%d\n", ans);
	}
	
	return 0;
}