自动搬运

查看原文

来自洛谷，原作者为

	Hanx16Kira AFOed

搬运于2025-08-24 21:55:39，当前版本为作者最后更新于2024-01-05 21:12:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

[CTSC2012] 最短路

Luogu P4021

题目描述

给定一个节点 $1$ 和节点 $n$ 连通的正权无向图 $G$，请你删除不超过 $k$ 条边，使得节点 $1$ 和节点 $n$ 仍然连通的同时，且这两点之间的最短路尽可能长。

提交答案题。

Solution

模拟赛考到这道，改完这道题我爆了。

提交答案题一般是模拟退火逼近最优解，或者是观察数据特征求解。然后我在赛时敲了一个模拟退火，获得了 $42$ 分的高分（逃）。

谴责出题人不把评分标准告诉我。

尝试观察数据特征，接下来将会分别讨论每一个测试点的数据特征以及对应的解题策略。

测试点 1

数据范围很小，随便搜一下就可以很快的跑出答案。具体就是直接枚举每条边是否在答案出现，然后暴力跑一下最短路，取最优答案输出即可。随便跑跑就有解了。

代码没写。

测试点 2 / 3

虽然 $n,m$ 增大了，但是 $K$ 仍然不大，所以考虑继续搜。直接使用测试点 1 的做法跑的话根本跑不出来，考虑剪一下枝。

注意到每次删除掉的边显然只能够是当前最短路上的边，否则一定不优。所以每次删边时先用 Dijstra 找出最短路径，然后枚举路径上的边进行删除。

对于测试点 1 使用这个做法大约能在 $0.1$ 秒上下跑出答案，测试点 2 大约 $10$ 秒，测试点 3 大约 $12$ 分钟左右。

其实可以写成找到一个新答案就输出的形式，这样测试点 3 其实跑不到 $20$ 秒就能跑出最优解，求稳的话还是等跑完吧。

具体实现：

#include <bits/stdc++.h>
using namespace std;
const string file = "shortest3";
const int _N = 2e4 + 5, inf = 0x3f3f3f3f;
int N, M, K;
struct Edge {int nxt, to, w, id;} edge[_N];
int tot = 1, head[_N];
void addEdge(int x, int y, int w, int id) {
    edge[++tot] = {head[x], y, w, id}; head[x] = tot;
}
pair<vector<int>, int> getPath(vector<bool> &flag) {
    priority_queue<pair<int, int>> q;
    vector<bool> vis(N + 1, 0);
    vector<int> dist(N + 1, inf);
    vector<int> pre(N + 1, 0);
    dist[1] = 0; q.emplace(0, 1);
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = edge[i].nxt) {
            int v = edge[i].to, w = edge[i].w, id = i;
            if (!flag[edge[i].id]) continue;
            if (dist[v] > dist[x] + w) {
                dist[v] = dist[x] + w;
                pre[v] = id;
                q.emplace(-dist[v], v);
            }
        }
    }
    vector<int> res;
    for (int x = N; x; x = edge[pre[x]^1].to)
        if (pre[x]) res.emplace_back(edge[pre[x]].id);
    return {res, dist[N]};
}
int ans = 0;
vector<bool> finFlag;
void dfs(int k, vector<bool> &flag) {
    auto res = getPath(flag);
    if (res.second == inf) return ;
    if (k == K + 1) {
        if (res.second > ans) {
            finFlag = flag, ans = res.second;
            vector<int> res;
            for (int i = 1; i <= M; ++i) if (!finFlag[i])
                res.emplace_back(i);
            ofstream fout(file + ".out");
            fout << res.size() << '\n';
            for (int x: res) fout << x << '\n';
            fout.close();
        }
        return ;
    }
    for (int x: res.first) {
        flag[x] = 0;
        dfs(k + 1, flag);
        flag[x] = 1;
    }
}
signed main() {
    ifstream fin(file + ".in");
    fin >> N >> M >> K;
    for (int i = 1; i <= M; ++i) {
        int x, y, w; fin >> x >> y >> w;
        addEdge(x, y, w, i), addEdge(y, x, w, i);
    }
    fin.close();
    vector<bool> tmp(M + 1, 1);
    dfs(1, tmp);
}

测试点 4

发现 $m=k$，也就是删边无限制，换言之就是要求出一条从 $1$ 到 $n$ 的最长路径。因为 $n=20$，所以可以直接状压 DP 解决。设 $f(i,S)$ 表示当前在 $i$，经过的点集为 $S$，转移 $f(i,S)+d(i,j)\to f(j,S\cup \{j\})$。可以在 $1$ 秒内得到解。

#include <bits/stdc++.h>
using namespace std;
const int _N = 20 + 1;
int f[_N][_N], id[_N][_N], N, M, K;
int F[_N][1 << _N];
pair<int, int> pre[_N][1 << _N];
signed main() {
    freopen("shortest4.in", "r", stdin);
    freopen("shortest4.out", "w", stdout);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    memset(f, 0xcf, sizeof f);
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        if (w > f[x][y]) {
            f[x][y] = f[y][x] = w;
            id[x][y] = id[y][x] = i;
        }
    }
    vector<int> S;
    for (int i = 1; i < (1 << N); ++i) S.emplace_back(i);
    sort(S.begin(), S.end(), [](const int &i, const int &j) {
        return __builtin_popcount(i) < __builtin_popcount(j);
    });
    memset(F, 0xcf, sizeof F);
    F[1][1] = 0;
    for (int s: S) {
        for (int i = 1; i <= N; ++i) if ((s >> (i - 1)) & 1) {
            for (int j = 1; j <= N; ++j) {
                if ((s >> (j - 1)) & 1) continue;
                int ts = s | (1 << (j - 1));
                if (F[i][s] + f[i][j] > F[j][ts]) {
                    F[j][ts] = F[i][s] + f[i][j];
                    pre[j][ts] = {i, s};
                }
            }
        }
    }
    int pos = max_element(F[N] + 1, F[N] + (1 << N)) - F[N];
    vector<bool> res(M + 1, 0);
    for (pair<int, int> x(N, pos); x.first; x = pre[x.first][x.second]) {
        int lst = pre[x.first][x.second].first;
        if (lst) res[id[lst][x.first]] = 1;
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!res[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 5

这个点其实与测试点 4 类似，虽然表面上很难看出来。这个点中 $1000$ 个点被划分成为了 $50$ 个块，每个块内有 $20$ 个点，相邻块间有 $1$ 条边。

具体做法与测试点 4 类似，先对每一个块跑出最优解，然后把所有块的解拼在一起即可。

一个块跑 $1$ 秒左右，$50$ 个块可以在 $1$ 分钟内跑出来。

#include <bits/stdc++.h>
using namespace std;
const int _N = 2e4 + 5;
int N, M, K, len = 20, bl[_N];
struct Edge {int x, y, w, id;} edge[_N];
vector<Edge> vec[_N];
int f[21][1 << 21], d[21][21], num[21][21];
pair<int, int> pre[21][1 << 21];
vector<int> S;
bool flag[_N];
void solve(int id) {
    memset(f, 0xcf, sizeof f), memset(d, 0xcf, sizeof d), memset(num, 0, sizeof num);
    for (int i = 0; i <= len; ++i) for (int s = 0; s < (1 << len); ++s)
        pre[i][s] = {0, 0};
    for (auto e: vec[id]) {
        int x = e.x, y = e.y, w = e.w, i = e.id;
        x -= (id - 1) * len, y -= (id - 1) * len;
        if (w > d[x][y]) {
            d[y][x] = d[x][y] = w;
            num[y][x] = num[x][y] = i;
        }
    }
    f[1][1] = 0;
    for (int s: S)
        for (int i = 1; i <= len; ++i) if (s >> (i - 1) & 1)
            for (int j = 1; j <= len; ++j) {
                if (s >> (j - 1) & 1) continue;
                int ts = s | (1 << (j - 1));
                if (f[i][s] + d[i][j] > f[j][ts]) {
                    f[j][ts] = f[i][s] + d[i][j];
                    pre[j][ts] = {i, s};
                }
            }
    int pos = max_element(f[len] + 1, f[len] + (1 << len)) - f[len];
    cerr << id << ": " << f[len][pos] << '\n';
    for (pair<int, int> x(len, pos); x.first; x = pre[x.first][x.second]) {
        int lst = pre[x.first][x.second].first;
        if (lst) flag[num[lst][x.first]] = 1;
    }
}
signed main() {
    freopen("shortest5.in", "r", stdin);
    freopen("shortest5.out", "w", stdout);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++i) bl[i] = (i - 1) / len + 1;
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        if (bl[x] == bl[y])
            vec[bl[x]].push_back({x, y, w, i});
        else flag[i] = 1;
    }
    for (int i = 1; i < (1 << len); ++i)
        S.emplace_back(i);
    sort(S.begin(), S.end(), [](const int& i, const int& j) {
        return __builtin_popcount(i) < __builtin_popcount(j);
    });
    for (int i = 1; i <= N / len; ++i) solve(i);
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!flag[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 6 / 7

这两个点特征与测试点 5 类似，为 $1000$ 个点被分为了 $100$ 个块，每个块内有 $10$ 个点，相邻块间有 $1$ 条边，块内分别有 $10$ 条边（测试点 6）和 $20$ 条边（测试点 7）。但是这两个点不保证 $m=k$，因此不能直接状压 DP。

因为每个块内的边数和点数很少，所以可以使用测试点 1 的做法跑出每个块 $i$ 删除 $j$ 条边时的答案 $f(i,j)$，然后对于所有块做背包即可。

每个块 $0.6$ 秒上下，所有块能在 $1$ 分钟左右跑完。

#include <bits/stdc++.h>
using namespace std;
const int _N = 2e4 + 5, inf = 0x3f3f3f3f;
int N, M, K, bl[_N];
struct Edge {int x, y, w, id;};
vector<Edge> vec[101];
bool flag[_N];
int dist[21];
vector<pair<int, int>> e[21];
bool vis[_N];
void dij() {
    memset(vis, 0, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<pair<int, int>> q;
    q.emplace(0, 1); dist[1] = 0;
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (auto [v, w]: e[x]) if (dist[v] > dist[x] + w) {
            dist[v] = dist[x] + w;
            q.emplace(-dist[v], v);
        }
    }
}
int met[101][21];
int val[101][21];
int tot = 20;
void getVal(int id) {
    memset(val[id], 0xcf, sizeof val[id]);
    for (int S = 0; S < (1 << tot); ++S) {
        for (int i = 1; i <= 10; ++i) e[i].clear();
        for (int i = 0; i < tot; ++i) if (S & (1 << i)) {
            int x = vec[id][i].x - 10 * (id - 1), y = vec[id][i].y - 10 * (id - 1), w = vec[id][i].w;
            e[x].emplace_back(y, w), e[y].emplace_back(x, w);
        }
        dij();
        int cnt = tot - __builtin_popcount(S);
        if (dist[10] != inf && dist[10] > val[id][cnt])
            val[id][cnt] = dist[10], met[id][cnt] = S;
    }
}
int f[101][_N], pre[101][_N];
signed main() {
    freopen("shortest7.in", "r", stdin);
    freopen("shortest7.out", "w", stdout);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++i) bl[i] = (i - 1) / 10 + 1;
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        if (bl[x] == bl[y])
            vec[bl[x]].push_back({x, y, w, i});
        else flag[i] = 1;
    }
    for (int i = 1; i <= 100; ++i) getVal(i);
    memset(f, 0xcf, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= 100; ++i) {
        for (int j = 0; j <= K; ++j) {
            for (int t = 0; t <= min(j, tot); ++t) {
                int res = f[i-1][j-t] + val[i][t];
                if (res > f[i][j])
                    f[i][j] = res, pre[i][j] = t;
            }
        }
    }
    int pos = max_element(f[100], f[100] + K + 1) - f[100];
    for (int i = 100; i; --i) {
        int S = met[i][pre[i][pos]];
        for (int j = 0; j < tot; ++j) if (S & (1 << j))
            flag[vec[i][j].id] = 1;
        pos = pos - pre[i][pos];
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!flag[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 8

这个测试点其实是一个 $100$ 行 $100$ 列的网格图。手模较小的数据，比如 $n$ 行 $n$ 列（$n$ 为偶数），容易发现答案为 $n^2-2$，并得出构造方法，且无法构造出 $n^2-1$ 的解。

这个比较好写。

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
inline pii id(int x) {return {(x - 1) / 100 + 1, (x - 1) % 100 + 1};}
int N, M, K;
map<pair<pii, pii>, int> mp;
signed main() {
    freopen("shortest8.in", "r", stdin);
    freopen("shortest8.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M >> K;
    vector<bool> rem(M + 1, 0);
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        mp[{id(x), id(y)}] = mp[{id(y), id(x)}] = i;
    }
    for (int i = 1; i <= 98; ++i) {
        for (int j = 1; j <= 99; ++j)
            rem[mp[{{i, j}, {i, j + 1}}]] = 1;
        if (i & 1) rem[mp[{{i, 100}, {i + 1, 100}}]] = 1;
        else rem[mp[{{i, 1}, {i + 1, 1}}]] = 1;
    }
    for (int i = 1; i <= 99; ++i) {
        rem[mp[{{99, i}, {100, i}}]] = 1;
        if (i & 1) rem[mp[{{100, i}, {100, i + 1}}]] = 1;
        else rem[mp[{{99, i}, {99, i + 1}}]] = 1;
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!rem[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 9

这个点是一个 $2$ 行 $1000$ 列，被删去了很少边的网格图。将删去的边的边权设为 $-\infty$，设 $a(i,j)$ 表示 $(i,j)\to(i,j+1)$ 的边权，$b(i)$ 表示 $(0,i)\to(1,i)$ 的边权，那么不难有一个 DP：

设 $f(i,j)$ 表示 $(1,1)\to(i,j)$ 的最优解，那么有转移：

$$\begin{array}{rll} f(0,i)&\gets&\max\{f(0,i-1)+a(0,i-1),f(1,i-1)+a(1,i-1)+b(i)\}\\ f(1,i)&\gets&\max\{f(0,i-1)+a(0,i-1)+b(i),f(1,i-1)+a(1,i-1)\} \end{array} $$

记录一下决策点以便输出方案。

#include <bits/stdc++.h>
using namespace std;
int N, M, K;
int a[2][1005], b[1005], f[2][1005];
int ida[2][1005], idb[1005];
int pre[2][1005];
signed main() {
    freopen("shortest9.in", "r", stdin);
    freopen("shortest9.out", "w", stdout);
    cin >> N >> M >> K;
    memset(a, 0xcf, sizeof a), memset(b, 0xcf, sizeof b);
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        if (y - x == 1) a[x > 1000][x % 1000] = w, ida[x > 1000][x % 1000] = i;
        else b[x] = w, idb[x] = i;
    }
    f[1][0] = 0, f[1][1] = b[1];
    for (int i = 2; i <= 1000; ++i) {
        {
            int res1 = f[0][i-1] + a[0][i-1];
            int res2 = f[1][i-1] + a[1][i-1] + b[i];
            if (res1 < res2) f[0][i] = res2, pre[0][i] = 1;
            else f[0][i] = res1, pre[0][i] = 0;
        } {
            int res1 = f[0][i-1] + a[0][i-1] + b[i];
            int res2 = f[1][i-1] + a[1][i-1];
            if (res1 < res2) f[1][i] = res2, pre[1][i] = 1;
            else f[1][i] = res1, pre[1][i] = 0;
        }
    }
    cerr << f[1][1000] << '\n';
    vector<bool> rem(M + 1, 0);
    int pos = 1;
    for (int i = 1000; i; --i) {
        if (pos ^ pre[pos][i]) {
            rem[idb[i]] = 1;
            rem[ida[pos^1][i-1]] = 1;
        } else rem[ida[pos][i-1]] = 1;
        pos = pre[pos][i];
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!rem[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 10

看起来数据毫无规律，但是 $m-k=n-1$，所以不妨猜这张图存在一条哈密顿路，事实证明也确实如此。

但是直接搜哈密顿路也是根本搜不出来的（至少我没搜出来），发现 $k=100$，也就是说其实有很多点的度数都是 $2$ 及以下的，这些点连接的边肯定是不能够被删掉的，所以只需要关心那些度数大于 $2$ 的点。

写个程序跑一下发现度数大于 $2$ 的点数量为 $200$，也就是说所有的非法点度数都为 $3$。由于度数为 $2$ 的点连接的边不能够被删掉，因此可以被删掉的边一定两侧点的度数都为 $3$。再跑一下发现这样的边数量仅有 $101$ 条，也就是说只需要从这 $101$ 条边中选一条删掉就行了。所以直接枚举删掉哪一条边，然后暴力 check 一下就行了。

#include <bits/stdc++.h>
using namespace std;
const int _N = 2e4 + 5;
int N, M, K, deg[_N];
vector<pair<int, int>> e[_N];
bool flag[_N];
signed main() {
    freopen("shortest10.in", "r", stdin);
    freopen("shortest10.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M >> K;
    fill(flag + 1, flag + M + 1, 1);
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        e[x].emplace_back(y, i), e[y].emplace_back(x, i);
        ++deg[x], ++deg[y];
    }
    map<int, int> mp;
    vector<int> vec;
    for (int i = 1; i <= N; ++i) if (deg[i] > 2) {
        for (auto [v, id]: e[i]) if (deg[v] > 2 && i < v)
            vec.emplace_back(id), flag[id] = 0;
    }
    auto check = [&]()->bool {
        int d = 0;
        vector<bool> vis(N + 1, 0);
        auto dfs = [&](const auto &dfs, int x, int dep)->void {
            if (x == N) d = dep;
            vis[x] = 1;
            for (auto [v, id]: e[x]) if (flag[id] && !vis[v])
                dfs(dfs, v, dep + 1);
        };
        dfs(dfs, 1, 1);
        return d == N;
    };
    for (int x: vec) {
        flag[x] = 1;
        if (check()) break;
        flag[x] = 0;
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!flag[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

不得不说，写一道提答题感觉像是写了一整场模拟赛的暴力一样，一道题里面同时有很多个不同的问题。