「NOI2020」翻修道路 题解
2026-10-11 22:10:30
发布于：湖北
5阅读
0回复
0点赞
题目链接：「NOI2020」翻修道路
题目难度：
题目大意
给一个无向图，要找一条从 S 到 T 的路径，使得删掉这条路径上的所有边之后，剩下的图仍然连通，并且路径总长度最小。如果找不到就输出 -1。
核心难点
一开始我以为直接跑最短路就完事了，结果发现删边之后图可能断掉。所以路径不能随便选，必须避开那些“删掉就会让图不连通”的边或点。
具体来说，有两类东西要避开：
- 割点：如果路径经过割点，删掉路径后割点会把图分成几块，肯定不连通。
- 分离边对：有些边单独删没事，但两条边同时删就会把图割开。这种边对不能同时出现在路径里。
算法流程
1. 找割点（Tarjan）
先跑一遍 Tarjan，把除了 S 和 T 之外的割点都标记成 bad。这些点不能出现在路径上。
void get_bad_vertices(int x) {
if (x == T) has_T[x] = 1;
dfn[x] = low[x] = dfn_cnt++;
int cnt = 0;
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (!~dfn[y]) {
get_bad_vertices(y);
if (has_T[y]) has_T[x] = 1;
// 如果子树能到 T，或者 low[y] < dfn[x]，说明 x 可能是割点
if (has_T[y] || low[y] < dfn[x]) {
cnt += buffer[x];
chkmin(low[x], low[y]);
}
buffer[x] = 0;
} else if (dfn[y] < dfn[x]) {
++cnt;
++buffer[y];
chkmin(low[x], dfn[y]);
}
}
if (cnt <= 2 && x != S && x != T) {
bad[x] = 1; // 标记为割点
}
}
2. 跑初始最短路（避开割点）
在避开 bad 点的图上跑 Dijkstra，得到一条从 S 到 T 的最短路，同时记录路径。
inline void get_path() {
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> q;
memset(dis, oo, sizeof(dis[0]) * n);
q.push(mp(0, S));
dis[S] = 0;
while (!q.empty()) {
int x = q.top().y; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (!bad[y] && chkmin(dis[y], dis[x] + e[i].g)) {
pre[y] = i ^ 1;
q.push(mp(dis[y], y));
}
}
}
// 从 T 回溯到 S，记录路径上的点和边
pathn = 0;
int cur = T;
while (cur != S) {
path[pathn++] = cur;
on_path[pre[cur] >> 1] = 1;
cur = e[pre[cur]].id;
}
path[pathn++] = cur;
reverse(path, path + pathn);
REP(i, 0, pathn) id[path[i]] = i;
}
3. 分析非路径边，找“坏对”
路径上的点已经确定了，接下来要分析那些不在路径上的边。这些边可能把路径上的某些点“连起来”，如果两条这样的边同时被删，可能会把图割开。
void get_bad_pairs(int x) {
dfn[x] = low[x] = dfn_cnt++;
vector<int> up;
for (int i = st[x]; ~i; i = e[i].nxt)
if (!on_path[i >> 1]) { // 只看非路径边
int y = e[i].id;
if (~dfn[y] && dfn[y] < dfn[x]) {
if (SZ(down[y]) <= 2) down[y].pb(i ^ 1);
chkmin(low[x], dfn[y]);
if (SZ(up) <= 2) up.pb(i);
} else {
if (!~dfn[y]) {
get_bad_pairs(y);
if (low[y] < dfn[x]) {
up.insert(up.end(), ALL(down[x]));
chkmin(low[x], low[y]);
} else {
if (!~id[x]) set_bad_pair(down[x]);
}
down[x].clear();
}
}
}
if (!~id[x]) set_bad_pair(up);
}
这段有点像 Tarjan 的变种，目的是找出那些“如果同时删掉就会出问题”的边对，存到 bad_pair 里。
4. 并查集检查连通性
把路径上的边全部去掉，用并查集看看剩下的图是否连通。
REP(i, 0, n) fa[i] = i;
REP(i, 0, n)
for (int j = st[i]; ~j; j = e[j].nxt)
if (!on_path[j >> 1])
fa[get(i)] = get(e[j].id);
bool not_connected = 0;
REP(i, 0, n) if (get(i) != get(0)) {
not_connected = 1;
break;
}
5. 如果连通，直接输出最短路，否则跑带约束的最短路
如果去掉路径边后图还连通，那初始最短路就是答案。否则，需要用带状态的最短路，把 bad_pair 约束考虑进去。
inline LL work() {
priority_queue<pair<LL, pair<int, int>>, vector<pair<LL, pair<int, int>>>, greater<pair<LL, pair<int, int>>>> q;
q.push(mp(0, mp(S, 0)));
while (!q.empty()) {
LL d = q.top().x;
int x = q.top().y.x, lst = q.top().y.y;
q.pop();
if (x == T) return d;
// 状态剪枝：每个点最多访问两次，保留更优的 lst
if (!vis[x]) info[x] = lst;
else if (vis[x] == 1) {
if (~id[x]) { if (lim[lst] <= lim[info[x]]) continue; }
else { if (lst >= info[x]) continue; }
} else if (vis[x] > 1) continue;
++vis[x];
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (bad[y]) continue;
if (~id[y]) {
// 不能同时走 bad_pair 里的两条边
if (~bad_pair[i] && path[lst] == e[bad_pair[i]].id) continue;
if (id[y] == lst) continue;
if (!on_path[i >> 1]) q.push(mp(d + e[i].g, mp(y, id[y])));
else if (id[y] < lim[lst]) q.push(mp(d + e[i].g, mp(y, lst)));
} else {
if (~id[x]) q.push(mp(d + e[i].g, mp(y, id[x])));
else q.push(mp(d + e[i].g, mp(y, lst)));
}
}
}
return -1;
}
这里 lim 数组是在 get_lim() 里算出来的，用来限制路径上的前进方向，避免走回头路导致重复经过某些边。
Code
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) {
return b < a ? a = b, 1 : 0;
}
template<typename T> inline bool chkmax(T &a, const T &b) {
return a < b ? a = b, 1 : 0;
}
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int maxn = 500010, maxm = 1000100;
struct edge {
int id, g, nxt;
edge() { }
edge(int _id, int _g, int _nxt): id(_id), g(_g), nxt(_nxt) { }
};
int en;
int st[maxn + 5];
edge e[(maxm << 1) + 5];
inline void add_edge(int x, int y, int z) {
e[en] = edge/*(码农爱历史)*/(y, z, st[x]), st[x] = en++;
}
int n, m;
int S, T;
bool bad[maxn + 5];
int buffer[maxn + 5];
int dfn_cnt = 0;
int dfn[maxn + 5], low[maxn + 5];
bool has_T[maxn + 5];
// Tarjan 找割点
void get_bad_vertices(int x) {
if (x == T) has_T[x] = 1;
dfn[x] = low[x] = dfn_cnt++;
int cnt = 0;
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (!~dfn[y]) {
get_bad_vertices(y);
if (has_T[y]) has_T[x] = 1;
if (has_T[y] || low[y] < dfn[x]) {
cnt += buffer[x];
chkmin(low[x], low[y]);
}
buffer[x] = 0;
} else if (dfn[y] < dfn[x]) {
++cnt;
++buffer[y];
chkmin(low[x], dfn[y]);
}
}
if (cnt <= 2 && x != S && x != T) {
bad[x] = 1;
}
}
LL dis[maxn + 5];
bool on_path[maxm + 5];
int pathn;
int path[maxn + 5];
int id[maxn + 5];
// 跑最短路并记录路径
inline void get_path(/*(码农爱历史)*/) {
static bool vis[maxn + 5];
static int pre[maxn + 5];
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> q;
memset(dis, oo, sizeof(dis[0]) * n);
memset(vis, 0, sizeof(vis[0]) * n);
q.push(mp(0, S));
dis[S] = 0;
while (!q.empty()) {
int x = q.top().y;
q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (!bad[y] && chkmin(dis[y], dis[x] + e[i].g)) {
pre[y] = i ^ 1;
q.push(mp(dis[y], y));
}
}
}
memset(on_path, 0, sizeof(on_path[0]) * m);
pathn = 0;
int cur = T;
while (cur != S) {
path[pathn++] = cur;
on_path[pre[cur] >> 1] = 1;
cur = e[pre[cur]].id;
}
path[pathn++] = cur;
reverse(path, path + pathn);
memset(id, -1, sizeof(id[0]) * n);
REP(i, 0, pathn) id[path[i]] = i;
}
int bad_pair[(maxm << 1) + 5];
vector<int> down[maxn + 5];
inline void set_bad_pair(const vector<int> &v) {
if (SZ(v) != 2) return;
bad_pair[v[0]] = v[1];
bad_pair[v[1]] = v[0];
}
// 找坏边对
void get_bad_pairs(int x) {
dfn[x] = low[x] = dfn_cnt++;
vector<int> up;
for (int i = st[x]; ~i; i = e[i].nxt)
if (!on_path[i >> 1]) {
int y = e[i].id;
if (~dfn[y] && dfn[y] < dfn[x]) {
if (SZ(down[y]) <= 2) down[y].pb(i ^ 1);
chkmin(low[x], dfn[y]);
if (SZ(up) <= 2) up.pb(i);
} else {
if (!~dfn[y]) {
get_bad_pairs(y);
if (low[y] < dfn[x]) {
up.insert(up.end(), ALL(down[x]));
chkmin(/*(码农爱历史)*/low[x], low[y]);
} else {
if (!~id[x]) set_bad_pair(down[x]);
}
down[x].clear();
}
}
}
if (!~id[x]) set_bad_pair(up);
}
int fa[maxn + 5];
int get(int x) {
return fa[x] == x ? x : fa[x] = get(fa[x]);
}
int lim[maxn + 5];
// 计算路径上前进限制
inline bool get_lim() {
static bool leftmost[maxn + 5], rightmost[maxn + 5];
static bool vis[maxn + 5];
memset(leftmost, 0, sizeof(leftmost[0]) * pathn);
memset(rightmost, 0, sizeof(rightmost[0]) * pathn);
memset(vis, 0, sizeof(vis[0]) * n);
REP(i, 0, pathn) {
if (!vis[get(path[i])]) {
leftmost[i] = 1;
vis[get(path[i])] = 1;
}
}
memset(vis, 0, sizeof(vis[0]) * n);
for (int i = pathn - 1; i >= 0; --i) {
if (!vis[get(path[i])]) {
rightmost[i] = 1;
vis[get(path[i])] = 1;
}
}
if (leftmost[pathn - 1] || rightmost[0]) return 0;
REP(i, 0, pathn + 1) lim[i] = pathn;
int lst = -1;
REP(i, 0, pathn) {
if (leftmost[i]) lst = i;
if (rightmost[i]) {
if (lst > 0 && i + 1 < pathn) {
lim[lst - 1] = i + 1;
}
}
}
for (int i = pathn - 1; i >= 0; --i) {
chkmin(lim[i], lim[i + 1]);
}
return 1;
}
// 带状态的最短路
inline LL work() {
cout << "请勿抄题解代码";//请你发现后删除，否则错(码农爱历史)
static int vis[maxn + 5];
static int info[maxn + 5];
priority_queue<pair<LL, pair<int, int>>, vector<pair<LL, pair<int, int>>>, greater<pair<LL, pair<int, int>>>> q;
memset(vis, 0, sizeof(vis[0]) * n);
q.push(mp(0, mp(S, 0)));
while (!q.empty()) {
LL d = q.top().x;
int x = q.top().y.x, lst = q.top().y.y;
q.pop();
if (x == T) return d;
if (!vis[x]) info[x] = lst;
else if (vis[x] == 1) {
if (~id[x]) {
if (lim[lst] <= lim[info[x]]) continue;
} else {
if (lst >= info[x]) continue;
}
} else if (vis[x] > 1) continue;
++vis[x];
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (bad[y]) continue;
if (~id[y]) {
if (~bad_pair[i] && path[lst] == e[bad_pair[i]].id) continue;
if (id[y] == lst) continue;
if (!on_path[i >> 1]) {
q.push(mp(d + e[i].g, mp(y, id[y])));
} else if (id[y] < lim[lst]) {
q.push(mp(d + e[i].g, mp(y, lst)));
}
} else {/*(码农爱历史)*/
if (~id[x]) q.push(mp(d + e[i].g, mp(y, id[x])));
else q.push(mp(d + e[i].g, mp(y, lst)));
}
}
}
return -1;
}
int main() {
scanf("%d%d", &n, &m);
memset(st, -1, sizeof(st[0]) * n), en = 0;
REP(i, 0, m) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z), --x, --y;
add_edge(x, y, z);
add_edge(y, x, z);
}
scanf("%d%d", &S, &T), --S, --T;
memset(buffer, 0, sizeof(buffer[0]) * n);
memset(dfn, -1, sizeof(dfn[0]) * n);
memset(bad, 0, sizeof(bad[0]) * n);
memset(has_T, 0, sizeof(has_T[0]) * n);
dfn_cnt = 0;
get_bad_vertices(S);
get_path();
REP(i, 0, n) fa[i] = i;
REP(i, 0, n)
for (int j = st[i]; ~j; j = e[j].nxt)
if (!on_path[j >> 1])
fa[get(i)] = get(e[j].id);
bool not_connected = 0;
REP(i, 0, n) if (get(i) != get(0)) {
not_connected = 1;
break;
}
REP(i, 0, n) down[i].clear();
memset(dfn, -1, sizeof(dfn[0]) * n);
memset(bad_pair, -1, sizeof(bad_pair[0]) * en);
dfn_cnt = 0;
REP(i, 0, pathn) if (!~dfn[path[i]])
get_bad_pairs(path[i]);
if (not_connected) {
get_lim();
printf("%lld\n", work());
} else {
printf("%lld\n", dis[T]);
}
return 0;
}
请大家踊跃质疑一下，我感觉哪里有点不严谨
100道题目竞赛 part 1（wece）
空白团队池：66个
有帮助，赞一个