自动搬运

查看原文

来自洛谷，原作者为

	five_rice_water 不进省队不改个签

搬运于2025-08-24 22:16:41，当前版本为作者最后更新于2025-03-21 13:53:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

洛谷P6029 题解

本人过的第一道黑题，也是本人在洛谷的第 $1000$ 道题。

这题其实不是很难，个人感觉到不了黑。

题意简述

对于一个有 $n$ 个点，$m$ 条边的无向图，可以交换 $k$ 对边的边权，问交换完的图上从 $1$ 号点到 $n$ 号点的最短路是多少。

思路

我们先来考虑和本题的思路部分很像的这样一道题：

现在有一个序列 $a$，可以交换任意两个数字 $k$ 次，问操作完之后的序列的最大子段和。数据保证 $1 \le n \le 500$。

不难发现，当 $k$ 过大的时候，这个问题没有意义。但是当 $k$ 相对小的时候，我们就要思考做法了。

一种相对可行的解法是这样的，我们枚举最终最大子段和所在的区间左右端点，再去考虑往这个区间里面交换前 $k$ 大的数字。

当然要考虑前 $k$ 大的数字有一部分已经在这个区间里面了，所以细节处理会麻烦一点，但总之是 $O(n^3)$ 左右可以解决的问题，不过该时间复杂度下对应数据范围可能会超时，但这不是我们这篇题解的核心内容，所以暂时不提。

总结一下，我们用到的思路是枚举终态，也就是考虑最终的答案可能来自哪些部分，然后进一步操作。

再简单一点，就是找一些能概括所有状态的情况，然后依次枚举所有情况，找到在该种情况的最优解，最后得到最终的最优解。

那么放到这道题上，到底哪些状态是有限可以被枚举同时可以概括所有情况的呢？

一种可行的情况是这张图上前 $p$ 短的边是否在从 $1$ 到 $n$ 的路径上。

这样枚举，可以概括所有的情况。

代码实现

第一步，我们要枚举 $p$，然后跑最短路。

但是我们已经知道了前 $p$ 短的路径了，有什么用呢？

我们可以用 dp 去获得“前 $p$ 短的路都在 $1$ 到 $n$ 的路径上时的最优解”。

怎么定义状态呢？我们设 $f_{i,j,t}$ 表示走过了 $j$ 条原本就是前 $p$ 短的边，并且使用了 $t$ 次魔法后，从 $1$ 走到 $i$ 的最小代价（不计算前 $p$ 短的边的长度）。

怎么转移呢？有以下两种情况。

当 $t+1\le k$ 时，可以尝试在 $x$ 到 $v$ 的路径上使用一次魔法，因为交换过来的边一定是前 $p$ 短的边的其中一根（否则答案一定不会更优），所以不记录答案，即更新 $f_{v,j,t+1}$ 的值为 $f_{x,j,t}$。

另外，当这条边是我们枚举的前 $p$ 条边中的其中一条时，因为是前 $p$ 短的边，所以不记录答案，我们可以更新 $f_{v,j+1,t}$ 的值为 $f_{x,j,t}$。

否则，这条边要计算到答案里，更新 $f_{v,j,t}$ 的值为 $f_{x,j,t} + w$。

最后，从 $1$ 到 $n$，走了 $j$ 条原本就是前 $p$ 小长度的边，用了 $k$ 次魔法的最小代价应该是 $f_{n,j,t} + sum_p$。其中 $sum_p$ 表示前 $p$ 小的边的长度和。

最后加上 $sum_p$ 的原因是在进行 dp 的过程中，不方便计算魔法交换过来的边的边权。

最后的答案就是所有 $j+t \le p$ 的 $f_{n,j,t}+sum_p$ 的最小值（因为超过范围的没有意义）。

代码展示

代码实现时注意一下边界处理，例如下面的 j+1<=m。

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
const int M = 155;
int n, m, k;

struct graph {
	int v, w, id;
};
vector<graph>e[N];

struct node {
	int x, j, k, dis;
	friend bool operator <(node a, node b) {
		return a.dis > b.dis;
	}
};

struct edge {
	int w, id;
} E[M];

bool cmp(edge a, edge b) {
	return a.w < b.w;
}
int mp[M], f[N][M][M], vis[N][M][M];

void dijkstra(int check) {
	memset(f, 0x3f, sizeof(f));
	memset(vis, 0, sizeof(vis));
	f[1][0][0] = 0;
	priority_queue<node>q;
	q.push({1, 0, 0, 0});
	while (!q.empty()) {
		node tmp = q.top();
		q.pop();
		int x = tmp.x;
		int j = tmp.j;
		int k_ = tmp.k;
		if (vis[x][j][k_])
			continue;
		vis[x][j][k_] = 1;
		for (int i = 0; i < e[x].size(); i++) {
			int v = e[x][i].v;
			int w = e[x][i].w;
			int id = e[x][i].id;
			if (k_ + 1 <= k && f[v][j][k_ + 1] > f[x][j][k_]) {
				f[v][j][k_ + 1] = f[x][j][k_];
				q.push({v, j, k_ + 1, f[v][j][k_ + 1]});
			}
			if (mp[id] <= check) {
				if (j + 1 <= m && f[v][j + 1][k_] > f[x][j][k_]) {
					f[v][j + 1][k_] = f[x][j][k_];
					q.push({v, j + 1, k_, f[v][j + 1][k_]});
				}
			} else {
				if (f[v][j][k_] > f[x][j][k_] + w) {
					f[v][j][k_] = f[x][j][k_] + w;
					q.push({v, j, k_, f[v][j][k_]});
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z, i});
		e[y].push_back({x, z, i});
		E[i] = {z, i};
	}
	sort(E + 1, E + 1 + m, cmp);
	for (int i = 1; i <= m; i++) {
		mp[E[i].id] = i;
	}
	int sum = 0;
	int ans = INT_MAX;
	for (int i = 0; i <= m; i++) {
		sum += E[i].w;
		dijkstra(i);
		for (int j = 0; j <= i; j++) {
			for (int K = 0; K <= k; K++) {
				if (j + K <= i) {
					ans = min(ans, f[n][j][K] + sum);
				} else
					break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}