題目

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