洛谷 P1186 玛丽卡(最短路,并查集,线段树)
题目链接
https://www.luogu.com.cn/problem/P1186
思路
因为边的数量 m ≤ n × ( n − 1 ) / 2 m \le n \times (n-1) / 2 m≤n×(n−1)/2,所以使用朴素Dijkstra更优。
我们先用Dijkstra求出 1 1 1号点到 n n n的最短路径。
我们枚举不在最短路径上的边,规定它是删除最短路径某一段后必定会走的边。这时我们只要找到该边替换的最短路径上的那一段路径,我们便可以知道删掉哪些边之后,最短路径会更新成经过该边的最短路径的距离,最后求一下最大值即可。
对于如何找到最短路径上被替换的那一段路径,我们可以考虑使用并查集来维护。我们规定每一个点的父亲为最短路上的前驱,最短路径上的点的父亲规定为自己(即最短路径上的点为祖先)。
线段树维护区间最大值:因为我们要替换的最短路径上的那一段路径必然是连续的,因此我们可以将最短路径上的边视为点,整条路径相当于一个区间。因此我们可以用线段树来维护区间最大值。
时间复杂度: O ( n 2 l o g 2 n ) O(n^{2}log_{2}n) O(n2log2n)
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e3 + 5, M = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, ans;
int dist1[N], distn[N], pre[N], f[N], pos[N], cnt;
bool st[N];
int mp[N][N];
int find(int x)
{
if (x != f[x])
f[x] = find(f[x]);
return f[x];
}
void dijkstra(int s, int d[])
{
fill(d + 1, d + n + 1, inf);
fill(st + 1, st + n + 1, false);
d[s] = 0;
for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if (!st[j] && (t == -1 || d[t] > d[j])) t = j;
}
st[t] = true;
for (int j = 1; j <= n; j++)
{
if (d[j] > d[t] + mp[t][j])
{
d[j] = d[t] + mp[t][j];
if (s == 1) pre[j] = t;
}
}
}
}
struct segmenttree
{
struct node
{
int l, r, maxx;
};
vector<node>tree;
segmenttree(): tree(1) {}
segmenttree(int n): tree(n * 4 + 1) {}
void pushup(int u)
{
auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];
root.maxx = max(left.maxx, right.maxx);
}
void pushdown(int u)
{
auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];
left.maxx = min(left.maxx, root.maxx);
right.maxx = min(right.maxx, root.maxx);
}
void build(int u, int l, int r)
{
auto &root = tree[u];
root = {l, r};
if (l == r)
{
root.maxx = inf;
}
else
{
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int val)
{
auto &root = tree[u];
if (root.l >= l && root.r <= r)
{
root.maxx = min(root.maxx, val);
return;
}
pushdown(u);
int mid = root.l + root.r >> 1;
if (l <= mid) modify(u << 1, l, r, val);
if (r > mid) modify(u << 1 | 1, l, r, val);
pushup(u);
}
int query(int u, int l, int r)
{
auto &root = tree[u];
if (root.l >= l && root.r <= r)
{
return root.maxx;
}
pushdown(u);
int mid = root.l + root.r >> 1;
int res = -inf;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res = max(res, query(u << 1 | 1, l, r));
return res;
}
};
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
fill(mp[i] + 1, mp[i] + n + 1, inf);
for (int i = 1, u, v, w; i <= m; i++)
{
cin >> u >> v >> w;
mp[u][v] = mp[v][u] = w;
}
dijkstra(1, dist1);
dijkstra(n, distn);
for (int i = 1; i <= n; i++)
f[i] = pre[i];
for (int i = n; i; i = pre[i])
{
pos[i] = ++cnt;//把路径抽象成区间上的点
f[i] = i;
if (pre[i])
{
mp[i][pre[i]] = mp[pre[i]][i] = inf;
}
}
segmenttree smt(n);
smt.build(1, 1, cnt);
for (int i = 1, u, v, w; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (mp[i][j] == inf) continue;
u = pos[find(i)];
v = pos[find(j)];
if (u == v) continue;
if (u > v) swap(u, v);
w = min(dist1[i] + mp[i][j] + distn[j], distn[i] + mp[i][j] + dist1[j]);
smt.modify(1, u + 1, v, w);
}
}
int ans = smt.query(1, 2, cnt);
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
// cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}