2021 CCF CSP-S2.廊桥分配

题目

4090. 廊桥分配

算法标签: 模拟, 贪心, 堆

思路

可以将每个飞机的起始时间和离开时间看作一个线段, 每个廊桥在同一时间只能服务一架飞机, 因为先到先得因此是按照起始时间进行排序

每个廊桥只关心最后一架飞机离开的时刻, 对于每个飞机有开始时间和离开时间, 对于每个空闲的廊桥来说, 安排到任意一个廊桥都是一样的, 朴素的做法是枚举国内分配廊桥的数量, 再枚举飞机, 但是时间复杂来到了$10^5\times 10^5$, 需要进行优化

因为放置到每个空闲廊桥是一样的, 因此可以按照廊桥编号从小到大放置飞机, 然后枚举分配给国内航班的廊桥数量, 维护两个小根堆分别代表使用的廊桥和空闲的廊桥, 时间复杂度$O(n\log n)$

代码

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

using namespace std;

const int N = 10010, M = 50010, K = 19, 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) {
   
			int mid = fa[v][k - 1];
			fa[v][k] = fa[mid][k - 1];
			f[v][k] = min(f[v][k - 1], f[mid][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);
	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;

	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);
		if (ans == INF) ans = -1;
		cout << ans << "\n";
	}

	return 0;
}