洛谷P1967 貨車運輸

傳送門

不愧是NOIP2013TG的題目。

solution:

為了讓車獲得最大的載重，他們走的路徑一定是這個圖的最大生成樹上的路徑。

那麼建樹，問題轉化為查詢樹上兩點間路徑上每條邊的邊權的最小值。

這不就是樹剖的闆子？但是我們發現這并不是維護點權，是維護邊權。

仔細思考發現，我們可以将每條邊的邊權轉到其深度較大的點上（即指派到兒子上）。

隻需要在對樹進行操作的時候（如用樹剖求兩點間所經過路徑的最小值）要注意避開 L C A ( x , y ) LCA(x, y) LCA(x,y)這個點。因為這個點代表的是 L C A ( x , y ) LCA(x, y) LCA(x,y)與其父親之間的邊，不應算入答案内。即在 d f s dfs dfs序上操作的時候應該不計其深度最低的一點。

當然我們發現，這題并不要求修改邊權。那麼我們也可以用樹上倍增預處理最值。原理與RMQ相像？

code:

// 這題使用RMQ求dfs序上的最小值，反正題目不要求修改。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100007;
const int LOGN = 20;
const int INF = 99999999;
int N, M, Q;
int value[MAXN];
struct Edge {
	int u, v, w, nxt;
	bool operator < (const Edge x) const {return w > x.w;}
	Edge (int u = 0, int v = 0, int w = 0, int nxt = 0) : u(u), v(v), w(w), nxt(nxt) {}
}e_for[MAXN], e[MAXN];
int fir[MAXN], tote;
int father[MAXN];
int book[MAXN], dep[MAXN], siz[MAXN], son[MAXN], fa[MAXN], top[MAXN], seg[MAXN], rev[MAXN], ti;
int lo[MAXN], f[MAXN][LOGN + 2];

void addedge(int x, int y, int z) {
	e[++tote] = Edge(x, y, z, fir[x]);
	fir[x] = tote;
}
int find(int x) {
	if(father[x] == x) return x;
	return father[x] = find(father[x]);
}
void kruscal() {
	for(int i = 1; i <= N; i++) father[i] = i;

	int tot = 0;
	for(int i = 1; i <= M; i++) {
		int x = e_for[i].u, y = e_for[i].v;
		int fx = find(x), fy = find(y);
		if(fx == fy) continue;
		father[fx] = fy; father[x] = fy;
		tot++;
		addedge(x, y, e_for[i].w);
		addedge(y, x, e_for[i].w);
		if(tot == N - 1) break;
	}
}
void dfs1(int x, int fath, int col) {
	book[x] = col;
	fa[x] = fath;
	dep[x] = dep[fath] + 1;
	siz[x] = 1;
	int mxid = 0, mx = 0;
	for(int i = fir[x]; i; i = e[i].nxt) {
		int y = e[i].v;
		if(y == fath) continue;
		dfs1(y, x, col);
		if(siz[y] > mx) mxid = y, mx = siz[y];
		siz[x] += siz[y];
	}
	son[x] = mxid;
}
void dfs2(int x, int topr) {
	top[x] = topr;
	seg[x] = ++ti;
	rev[ti] = x;
	if(!son[x]) return;
	dfs2(son[x], topr);
	for(int i = fir[x]; i; i = e[i].nxt) {
		int y = e[i].v;
		if(y == fa[x] || y == son[x]) continue;
		dfs2(y, y);
	}
}
void RMQ() {
	lo[0] = -1;
	for(int i = 1; i <= N; i++)
		lo[i] = lo[i >> 1] + 1;
	for(int j = 1; j <= LOGN; j++)
		for(int i = 1; i <= N; i++)
			f[i][j] = INF;
	for(int j = 1; j <= LOGN; j++)
		for(int i = 1; i + (1 << j) - 1 <= N; i++)
			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int query(int l, int r) {
	int k = lo[r - l + 1];
	return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int Query(int x, int y) {
	if(book[x] != book[y]) return -1;
	int mx = INF;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		mx = min(mx, query(seg[top[x]], seg[x]));
		x = fa[top[x]];
	}
	if(x == y) return mx;
	if(dep[x] < dep[y]) swap(x, y);
	mx = min(mx, query(seg[y] + 1, seg[x]));
	return mx;
}
int main() {
	#ifdef test
		freopen("test.txt", "r", stdin);
	#endif
	cin >> N >> M;
	int x, y, z;
	for(int i = 1; i <= M; i++) {
		scanf("%d %d %d", &x, &y, &z);
		e_for[i] = Edge(x, y, z, 0);
	}
	sort(e_for + 1, e_for + M + 1);
	kruscal();
	
	int col = 0;
	for(int i = 1; i <= N; i++)
		if(!book[i])
			dfs1(i, i, ++col);
	for(int i = 1; i <= N; i++)
		if(!top[i])
			dfs2(i, i);
	
	for(int i = 1; i <= N * 2; i++) {
		x = e[i].u, y = e[i].v;
		if(dep[x] < dep[y])
			f[seg[y]][0] = e[i].w;
	}
	RMQ();
	cin >> Q;
	for(int i = 1; i <= Q; i++) {
		scanf("%d %d", &x, &y);
		printf("%d\n", Query(x, y));
	}
	return 0;
}