当前位置：首页 > ops >正文

P1186 玛丽卡

ops 2025/6/20 20:46:34

题目

P1186 玛丽卡

算法标签: 最短路, 优化, 线段树

思路

根据题意, 计算的是删除任意一条边的最短路的最大值, 很明显删除最短路径以外的边才会对最短路有影响, 暴力的方法就是删除所有边, 每次删除一条边计算依次最短路
不难发现, 最终删边后的路径一定经过至少一条删边前最短路径之外的边，那么可以考虑经过一条确定边的最短路径
具体的算法思路

计算从节点 $1$ 到 $n$ 的最短路径 $d_1$ , 计算从节点 $n$ 到其他节点的最短路径 $d_2$
找到原最短路径的所有节点和边
对于每个非最短路径的边 $(u, v)$ , 计算能替代原最短路的哪些边
使用线段树维护每条边被删除后的最小替代值
计算最大值

时间复杂度 $O(n ^ 2 + m log n)$

代码

#include <bits/stdc++.h>using namespace std;typedef pair<int, int> PII;
const int N = 1010, INF = 0x3f3f3f3f;int n, m, w[N][N];
int dist_s[N], dist_t[N];
bool vis[N];
int tr[N << 2];
int ans;
int fa[N], pre[N], id[N], cnt;void dijkstra(int s, int d[]) {priority_queue<PII, vector<PII>, greater<>> q;memset(d, 0x3f, sizeof(int) * (n + 1));memset(vis, false, sizeof vis);d[s] = 0;q.push({0, s});while (!q.empty()) {auto [dis, u] = q.top();q.pop();if (vis[u]) continue;vis[u] = true;for (int v = 1; v <= n; ++v) {if (w[u][v] == INF) continue;if (d[u] + w[u][v] < d[v]) {d[v] = d[u] + w[u][v];if (s == 1) pre[v] = u;q.push({d[v], v});}}}
}int find(int u) {if (fa[u] != u) fa[u] = find(fa[u]);return fa[u];
}void build(int u, int l, int r) {tr[u] = INF;if (l == r) return;int mid = (l + r) >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);
}void add_tag(int u, int val) {tr[u] = min(tr[u], val);
}void push_down(int u) {if (tr[u] != INF) {add_tag(u << 1, tr[u]);add_tag(u << 1 | 1, tr[u]);tr[u] = INF;}
}void update(int u, int l, int r, int ql, int qr, int val) {if (l >= ql && r <= qr) {return add_tag(u, val);}push_down(u);int mid = (l + r) >> 1;if (ql <= mid) update(u << 1, l, mid, ql, qr, val);if (qr > mid) update(u << 1 | 1, mid + 1, r, ql, qr, val);
}void query(int u, int l, int r) {if (l == r) {ans = max(ans, tr[u]);return;}push_down(u);int mid = (l + r) >> 1;query(u << 1, l, mid);query(u << 1 | 1, mid + 1, r);
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;memset(w, 0x3f, sizeof w);for (int i = 0; i < m; ++i) {int u, v, val;cin >> u >> v >> val;if (w[u][v] > val) {w[u][v] = w[v][u] = val;}}dijkstra(1, dist_s);dijkstra(n, dist_t);for (int i = 1; i <= n; ++i) fa[i] = pre[i];// 从n向1号节点为每个节点分配编号for (int i = n; i != 0; i = pre[i]) {id[i] = ++cnt;fa[i] = i;// 移除最短路上的边if (pre[i]) {w[i][pre[i]] = w[pre[i]][i] = INF;}}if (cnt == 0) {cout << 0 << endl;return 0;}build(1, 2, cnt);for (int i = 1; i <= n; ++i) {for (int j = i + 1; j <= n; ++j) {// 跳过最短路上的边if (w[i][j] == INF) continue;int u = id[find(i)];int v = id[find(j)];if (u == v) continue;if (v < u) swap(u, v);int nw = min(dist_s[i] + w[i][j] + dist_t[j],dist_s[j] + w[i][j] + dist_t[i]);update(1, 2, cnt, u + 1, v, nw);}}ans = 0;query(1, 2, cnt);if (ans == INF) ans = 0;cout << ans << "\n";return 0;
}