[NOIP2013 提高组] 货车运输

• 2020 年 12 月 29 日
• 筆記
• LCA, 最小生成树

前言

使用算法：堆优化 \(prim\) ， \(LCA\) 。

题意

共有 \(n\) 个点，有 \(m\) 条边来连接这些点，每条边有权值。有 \(q\) 条类似于 \(u\) \(v\) 询问，求一条从 \(u\) 到 \(v\) 的路径使得路径上的最小权值最大，求这个最大值。若不存在从 \(u\) 到 \(v\) 的路径，则输出 \(-1\) 。

思路

先求该图的最大生成树，因为需要使得该路径上的最小值最大，而这条路径就是最小生成树的中两点的简单路径（最大生成树尽量取最大的边）。

故而，查询时的路径确定了，那么现在就是求这条路径的最小值了。
树上的距离操作离不开 \(LCA\) 。

假设查询 \(2\) 和 \(4\) 之间的距离最小值。那么它们之间的简单路径为 \(2->1->3->4\) ，可以分为两段：\(s->lca\) 和 \(lca->t\) 。这就是两条链，可以使用倍增求解。两条链的最小值一起来求最小值即可。

查询两个点是否在路径很简单，就是判断他们是否在一个连通块，直接在处理 \(prim\) 时一起求解即可。

C++代码

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define Swap(a, b) (a ^= b ^= a ^= b)
#define Min(a, b) ((a) < (b) ? (a) : (b)) 
void Quick_Read(int &N) {
	N = 0;
	int op = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-')
			op = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		N = (N << 1) + (N << 3) + (c ^ 48);
		c = getchar();
	}
	N *= op;
}
const int MAXN = 1e4 + 5;
const int MAXM = 40;
struct Node {
	int to, dist;
	Node() {}
	Node(int T, int D) {
		to = T;
		dist = D;
	}
	friend bool operator < (Node x, Node y) {
		return x.dist < y.dist;
	}
};
int fa[MAXN][MAXM], minn[MAXN][MAXM];
int de[MAXN];
vector<Node> v[MAXN];
priority_queue<Node> q;
bool vis[MAXN];
int dis[MAXN], belong[MAXN];
int ans, tot;
int n, m, t;
int LCA(int x, int y) {
	if(de[x] < de[y])
		Swap(x, y);
	for(int i = 30; i >= 0; i--)
		if(de[x] - (1 << i) >= de[y])
			x = fa[x][i];
	if(x == y)
		return x;
	for(int i = 30; i >= 0; i--) {
		if(fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}
int Climb(int x, int y) {
	int res = INF;
	for(int i = 30; i >= 0; i--)
		if(de[x] - (1 << i) >= de[y]) {
			res = Min(res, minn[x][i]);
			x = fa[x][i];
		}
	return res;
}
void Prim(int s) {
	tot++;
	dis[s] = 0;
	q.push(Node(s, 0));
	fa[s][0] = s;
	while(!q.empty()) {
		int now = q.top().to, adddist = q.top().dist;
		q.pop();
		if(vis[now])
			continue;
		belong[now] = tot;
		ans += adddist;
		vis[now] = true;
		int SIZ = v[now].size();
		for(int i = 0; i < SIZ; i++) {
			int next = v[now][i].to;
			if(v[now][i].dist > dis[next] && !vis[next]) {
				fa[next][0] = now;
				de[next] = de[now] + 1;
				minn[next][0] = v[now][i].dist;
				dis[next] = v[now][i].dist;
				q.push(Node(next, dis[next]));
			}
		}
	}
}
void Query() {
	int A, B;
	Quick_Read(t);
	for(int i = 1; i <= t; i++) {
		Quick_Read(A);
		Quick_Read(B);
		if(belong[A] != belong[B])
			printf("-1\n");
		else {
			int lca = LCA(A, B);
			int ans1 = Climb(A, lca);
			int ans2 = Climb(B, lca);
			printf("%d\n", Min(ans1, ans2));
		}
	}
}
void Build() {
	memset(dis, 128, sizeof(dis));
	for(int i = 1; i <= n; i++)
		if(!vis[i])
			Prim(i);
	for(int j = 1; j < 31; j++)
		for(int i = 1; i <= n; i++) {
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
			minn[i][j] = Min(minn[fa[i][j - 1]][j - 1], minn[i][j - 1]);
		}
}
void Read() {
	int A, B, C;
	Quick_Read(n);
	Quick_Read(m);
	for(int i = 1; i <= m; i++) {
		Quick_Read(A);
		Quick_Read(B); 
		Quick_Read(C);
		v[A].push_back(Node(B, C));
		v[B].push_back(Node(A, C));
	}
}
int main() {
	Read();
	Build();
	Query();
	return 0;
}