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;
}