NOIP2013提高组.货车运输

题目

506. 货车运输

算法标签: 并查集, 贪心, 树上倍增, 最小生成树, $lca$

思路

因为要求路径上$u$到$v$路径上最小承载路径最大, 首先要求的是两个点是连通的, 因此可以求最大生成树, 然后在最大生成树上求路径上的边的最小值, 由于树上两个点之间的路径是确定的, 因此可以使用倍增进行优化, 时间复杂度$O(n\log n)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 10010, M = 50010, K = 15, INF = 0x3f3f3f3f;

int n, m, q;
int head[N], ed[N << 1], ne[N << 1], w[N << 1], idx;
int fa[N][K], f[N][K], depth[N];
int p[N];

struct Edge {
   
	int u, v, w;

	bool operator<(const Edge &e) const {
   
		return w > e.w;
	}
} edges[M];

void add(int u, int v, int val) {
   
	ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

int find(int u) {
   
	if (p[u] != u) p[u] = find(p[u]);
	return p[u];
}

void kruskal() {
   
	sort(edges, edges + m);

	for (int i = 0; i < m; ++i) {
   
		auto [u, v, w] = edges[i];
		int fa1 = find(u);
		int fa2 = find(v);
		if (fa1 == fa2) continue;
		p[fa2] = fa1;
		add(u, v, w), add(v, u, w);
	}
}

void dfs(int u, int pre, int dep) {
   
	depth[u] = dep;
	for (int i = head[u]; ~i; i = ne[i]) {
   
		int v = ed[i];
		if (v == pre) continue;
		fa[v][0] = u;
		f[v][0] = w[i];
		for (int k = 1; k < K; ++k) {
   
			fa[v][k] = fa[fa[v][k - 1]][k - 1];
			f[v][k] = min(f[v][k - 1], f[fa[v][k - 1]][k - 1]);
		}
		dfs(v, u, dep + 1);
	}
}

int calc(int u, int v) {
   
	if (find(u) != find(v)) return -1;

	int ans = INF;
	if (depth[u] < depth[v]) swap(u, v);

	// 将u上提到与v相同深度
	for (int k = K - 1; k >= 0; --k) {
   
		if (depth[fa[u][k]] >= depth[v]) {
   
			ans = min(ans, f[u][k]);
			u = fa[u][k];
		}
	}

	if (u == v) return ans;

	// 同时上提u和v
	for (int k = K - 1; k >= 0; --k) {
   
		if (fa[u][k] != fa[v][k]) {
   
			ans = min({
   ans, f[u][k], f[v][k]});
			u = fa[u][k];
			v = fa[v][k];
		}
	}

	ans = min({
   ans, f[u][0], f[v][0]});
	return ans;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);
	memset(f, 0x3f, sizeof f);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) p[i] = i;
	for (int i = 0; i < m; ++i) {
   
		int u, v, w;
		cin >> u >> v >> w;
		edges[i] = {
   u, v, w};
	}

	kruskal();

	for (int i = 1; i <= n; ++i) {
   
		if (depth[i] == 0) dfs(i, -1, 1);
	}

	cin >> q;
	while (q--) {
   
		int u, v;
		cin >> u >> v;
		int ans = calc(u, v);
		cout << ans << "\n";
	}

	return 0;
}