题解：P7359 「JZOI-1」旅行

一道简单的倍增 dp 题。

Solution

考虑设

f_{i, j, 0/1, 0/1, 0/1}

，表示在第

i

个点，向上走

2^j

步，是从上到下还是从下到上，一开始是有船还是没船，最后是有船还是没船的最小代价。

考虑转移。我们先定义一个 merge 函数，表示合并两条路径。即

a_{0/1, 0/1}

和

b_{0/1, 0/1}

，将合并的结果给到

ans_{0/1, 0/1}

，注意必须是从

a

走到

b

。

容易写出：

CPP

long long temp[2][2];
void merge(long long ans[2][2], long long a[2][2], long long b[2][2]) {
	temp[0][0] = min(a[0][1] + b[1][0], a[0][0] + b[0][0]);
	temp[0][1] = min(a[0][1] + b[1][1], a[0][0] + b[0][1]);
	temp[1][0] = min(a[1][0] + b[0][0], a[1][1] + b[1][0]);
	temp[1][1] = min(a[1][1] + b[1][1], a[1][0] + b[0][1]);
	memcpy(ans, temp, sizeof(temp));
}

那么剩下的就是倍增了。都可以直接调用 merge 转移。看下代码，很简单易懂，没啥好说的。

时间复杂度

O(n\log_2 n)

。

AC Code

CPP

#include <bits/stdc++.h>
using namespace std;
#define f first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 2e5 + 5;
const long long INF = 1e11;
int n, L, q;
int h[N], e[N * 2], ne[N * 2], tp[N * 2], w[N * 2], z[N * 2], idx;
void add(int a, int b, int c, int d, int t) {
	e[idx] = b, w[idx] = c, z[idx] = d, tp[idx] = t, ne[idx] = h[a], h[a] = idx++;
} 
int f[N][21], dep[N];
long long g[2][N][21][2][2];
/*
g[0][i][j][0/1][0/1] 表示从上到下，一开始是否坐船，最后是否坐船。 
g[1][i][j][0/1][0/1] 表示从下到上，一开始是否坐船，最后是否坐船。 
*/
void dfs(int x, int fa) {
	f[x][0] = fa, dep[x] = dep[fa] + 1;
	for (int i = h[x]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == fa) continue;
		dfs(j, x);
		g[0][j][0][0][0] = w[i];
		g[0][j][0][0][1] = w[i] + L;
		g[1][j][0][0][0] = w[i];
		g[1][j][0][0][1] = w[i] + L;
		if (tp[i] == 1) {
			g[0][j][0][1][0] = w[i] - z[i];
			g[0][j][0][1][1] = w[i] - z[i];
			g[1][j][0][1][0] = w[i] + z[i];
			g[1][j][0][1][1] = w[i] + z[i];
		} else {
			g[0][j][0][1][0] = w[i] + z[i];
			g[0][j][0][1][1] = w[i] + z[i];
			g[1][j][0][1][0] = w[i] - z[i];
			g[1][j][0][1][1] = w[i] - z[i];
		}
	}
}
long long temp[2][2];
void merge(long long ans[2][2], long long a[2][2], long long b[2][2]) {
	temp[0][0] = min(a[0][1] + b[1][0], a[0][0] + b[0][0]);
	temp[0][1] = min(a[0][1] + b[1][1], a[0][0] + b[0][1]);
	temp[1][0] = min(a[1][0] + b[0][0], a[1][1] + b[1][0]);
	temp[1][1] = min(a[1][1] + b[1][1], a[1][0] + b[0][1]);
	memcpy(ans, temp, sizeof(temp));
}
int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	Dec(i, 20, 0) if (dep[f[x][i]] >= dep[y]) x = f[x][i];
	if (x == y) return x;
	Dec(i, 20, 0) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0]; 
}
long long work(int x, int y) {
	int sfa = lca(x, y);
	long long ans[2][2];
	ans[0][0] = 0, ans[0][1] = INF, ans[1][0] = INF, ans[1][1] = L;
	Dec(i, 20, 0) if (dep[f[x][i]] >= dep[sfa]) merge(ans, ans, g[1][x][i]), x = f[x][i]; 
	long long ans1[2][2];
	ans1[0][0] = 0, ans1[0][1] = INF, ans1[1][0] = INF, ans1[1][1] = 0;
	Dec(i, 20, 0) if (dep[f[y][i]] >= dep[sfa]) merge(ans1, g[0][y][i], ans1), y = f[y][i];
	long long res = INF;
	For(i, 0, 1) For(j, 0, 1) For(k, 0, 1) res = min(res, ans[i][j] + ans1[j][k]);
	return res;
}
int main() {
	//assert(freopen(".in", "r", stdin));
	//assert(freopen(".out", "w", stdout));
	cin.tie(nullptr)->sync_with_stdio(false);
	memset(h, -1, sizeof(h));
	cin >> n >> L >> q;
	For(i, 1, n - 1) {
		int x, y, a, z, tp;
		cin >> x >> y >> a >> z >> tp;
		add(x, y, a, z, tp);
		add(y, x, a, z, 1 - tp);
	}
	dfs(1, 0);
	For(i, 1, 20) {
		For(j, 1, n) {
			f[j][i] = f[f[j][i - 1]][i - 1];
			merge(g[0][j][i], g[0][f[j][i - 1]][i - 1], g[0][j][i - 1]);
			merge(g[1][j][i], g[1][j][i - 1], g[1][f[j][i - 1]][i - 1]);
		}
	}
	while (q--) {
		int u, v;
		cin >> u >> v;
		long long ans = work(u, v);
		cout << ans << '\n'; 
	}
	return 0;
}

题解：P7359 「JZOI-1」旅行

文章操作

Solution

相关推荐

评论

题解：P7359 「JZOI-1」旅行