题解【洛谷P6029】[JSOI2010]旅行

题面

简化版题意：给出 \(n\) 个点 \(m\) 条边的无向图，可以交换任意两条边的权值 \(k\) 次，求 \(1\) 结点到 \(n\) 结点的最短路。

考虑\(\text{DP}\)。

把所有的边从小到大排序，那么贪心的做的话，肯定有一个分界线 \(L\) ，使得 \(L\) 前面的边全部被使用，后面的边都不会被选用，我们枚举这个分界线 \(L\)。

设 \(dp_{i,j,k}\) 表示当前是 \(i\) 结点，使用了前 \(L\) 条边的 \(j\) 条，用了 \(k\) 次魔法。

可以在\(\text{Dijkstra}\)跑最短路时转移状态。

于是 \(\text{DP}\) 时出现了两种情况。

对于当前权值为 \(w\) 的边 \((u, v)\)：

这条边是前 \(L\) 条边中的一条：
- \(dp_{v,j + 1,k} = \min(dp_{v,j + 1,k}, dp_{u,j,k} + w)\)。
- 因为这条边和第 \(j + 1\) 条边一定会被选用，为了方便枚举，我们从小到大选用。
这条边不是前 \(L\) 条边中的一条：
- \(dp_{v,j,k} = \min(dp_{v,j,k}, dp_{u,j,k} + w)\) 直接使用这条边；
- \(dp_{v,j + 1,k + 1} = \min(dp_{v,j + 1,k + 1}, dp_{u,j,k} + w_{j + 1})\)将这条边与第 \(j + 1\) 条边交换。

代码写起来比较复杂。

#include <bits/stdc++.h>

#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)

#define itn int

#define gI gi

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

const int maxn = 166;

int n, m, k, tot, head[maxn], ver[maxn * 2], nxt[maxn * 2], edge[maxn * 2];

int dp[55][maxn][55], in[55][maxn][55], ans = 1000000007;

inline void add(int u, int v, int w)

{

	ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;

}

struct Node

{

	int u, v, w;

} e[maxn];

struct QwQ

{

	int u, j, k;

} ;

vector <int> vv[maxn]; 

inline bool cmp(Node x, Node y) {return x.w < y.w;}

inline void solve(int l)

{

	queue <QwQ> q;

	memset(dp, 0x3f, sizeof(dp));

	memset(in, 0, sizeof(in));

	in[1][0][0] = 1;

	dp[1][0][0] = 0;

	q.push((QwQ){1, 0, 0});

	while (!q.empty())

	{

		int u = q.front().u, j = q.front().j, kk = q.front().k;

		q.pop(); in[u][j][kk] = 0;

		for (int i = vv[u].size() - 1; i >= 0; i-=1)

		{

			int now = vv[u][i], v;

			if (u == e[now].u) v = e[now].v;

			else v = e[now].u;

			if (now <= l)

			{

				if (j < l && dp[v][j + 1][kk] > dp[u][j][kk] + e[j + 1].w)

				{

					dp[v][j + 1][kk] = dp[u][j][kk] + e[j + 1].w;

					if (!in[v][j + 1][kk])

					{

						in[v][j + 1][kk] = 1;

						q.push((QwQ){v, j + 1, kk});

					}

				}

			}

			else

			{

				if (j < l && kk < k && dp[v][j + 1][kk + 1] > dp[u][j][kk] + e[j + 1].w)

				{

					dp[v][j + 1][kk + 1] = dp[u][j][kk] + e[j + 1].w;

					if (!in[v][j + 1][kk + 1])

					{

						in[v][j + 1][kk + 1] = 1;

						q.push((QwQ){v, j + 1, kk + 1});

					}

				}

				if (dp[v][j][kk] > dp[u][j][kk] + e[now].w)

				{

					dp[v][j][kk] = dp[u][j][kk] + e[now].w;

					if (!in[v][j][kk])

					{

						in[v][j][kk] = 1;

						q.push((QwQ){v, j, kk});

					}

				}

			}

		}

	}

	for (int i = 0; i <= k; i+=1) ans = min(ans, dp[n][l][i]);

}

int main()

{

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	n = gi(), m = gi(), k = gi();

	for (int i = 1; i <= m; i+=1)

	{

		e[i].u = gi(), e[i].v = gi(), e[i].w = gi();

	}

	sort(e + 1, e + 1 + m, cmp);

	for (int i = 1; i <= m; i+=1)

		vv[e[i].u].push_back(i), vv[e[i].v].push_back(i);

	for (int i = 0; i <= m; i+=1) solve(i);

	printf("%d\n", ans);

	return 0;

}

巴特西

题解【洛谷P6029】[JSOI2010]旅行

最新文章

热门文章