解题思路

两点间路径的最长边最小，也就是等同于要求最小生成树。因此如果没有删边操作，那么只要\(Kruscal\)一遍就好了。

然而现在需要删边，也就是意味着最小生成树需要不停地重构……那怎么维护呢？

考虑离线，倒着处理所有的删边。于是乎就成为了一条一条加边。这就是标准的\(LCT\)动态维护最小生成树了。具体方法就是：如果两个点不在同一颗树中，那么\(link\)（注意，我们可以用\(findroot\)操作直接充当并查集的作用，常数稍大）；否则一定出现环，查询原本环中的最大边，如果大于当前边，那么\(cut\)那条边，\(link\)这条边。

因此，我们刚开始用所有不会被删去的边维护一个最小生成树（注意要用\(kruscal\)，不要动态维护，会被卡），然后再动态维护即可。

细节还是非常多的……

\(LCT\)维护点权最大值，如何来维护生成树呢？考虑将每条边变为一个点，也就是建立虚拟点，编号为\(i\)的边即为\(N+i\)。令虚拟点的权值为这条边的权值，原本的节点的权值为0，这样在查询路径上点权的最大值就好了。
如何确定被删除的边对应的权值是多少？一种思路是用邻接矩阵，要么就是用\(map\)
如果我们仅仅就是查找最大值，那么如何将其\(cut\)呢？显然我们不应该存值，而是应该存最大值的节点编号。

细节太恐怖了，调试了一晚上+一早上，结果发现是在判边的时候忘记用\(q[i]\)了……

反思

当在线无法处理的时候，可以考虑离线，将问题转化为已知的可解决的问题。

Code

/*By DennyQi 2018*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

typedef long long ll;

#define int long long

const int MAXN = 200010;

const int MAXM = 200010;

const int MAXS = MAXN+MAXM;

const int INF = 1061109567;

inline int Max(const int a, const int b){ return (a > b) ? a : b; }

inline int Min(const int a, const int b){ return (a < b) ? a : b; }

inline int read(){

    int x = 0; int w = 1; register char c = getchar();

    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());

    if(c == '-') w = -1, c = getchar();

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;

}

struct Edge{

	int u,v,w;

}e[MAXM];

int N,M,Q,top;

int X[MAXM],Y[MAXM],K[MAXM],val[MAXN],ans[MAXM],idmax[MAXS],q[MAXN];

bool used[MAXM];

map <pair<int,int>, int> E;

struct LinkCutTree{

	int fa[MAXS],ch[MAXS][2];

	bool tag[MAXS];

	inline bool rson(int f, int x){

		return ch[f][1] == x;

	}

	inline bool isroot(int x){

		return ch[fa[x]][rson(fa[x],x)] != x;

	}

	inline void pushup(int x){

		idmax[x] = x;

		if(val[idmax[ch[x][0]]] > val[idmax[x]]) idmax[x] = idmax[ch[x][0]];

		if(val[idmax[ch[x][1]]] > val[idmax[x]]) idmax[x] = idmax[ch[x][1]];

	}

	inline void rotate(int x){

		if(!x || !fa[x]) return;

		int f = fa[x], gf = fa[f];

		int p = rson(f, x), q = !p;

		if(!isroot(f)) ch[gf][rson(gf,f)] = x; fa[x] = gf;

		ch[f][p] = ch[x][q], fa[ch[x][q]] = f;

		ch[x][q] = f, fa[f] = x;

		pushup(f), pushup(x);

	}

	inline void reverse(int x){

		if(!isroot(x)) reverse(fa[x]);

		if(!tag[x]) return;

		tag[x] = 0;

		swap(ch[x][0], ch[x][1]);

		if(ch[x][0]) tag[ch[x][0]] ^= 1;

		if(ch[x][1]) tag[ch[x][1]] ^= 1;

	}

	inline void splay(int x){

		reverse(x);

		while(!isroot(x)){

			if(isroot(fa[x])){

				rotate(x); break;

			}

			if(rson(fa[fa[x]],fa[x]) ^ rson(fa[x],x)) rotate(x); else rotate(fa[x]);

			rotate(x);

		}

	}

	inline void access(int x){

		for(int y = 0; x; y = x, x = fa[x]){

			splay(x);

			ch[x][1] = y;

			pushup(x);

		}

	}

	inline void mroot(int x){

		access(x);

		splay(x);

		tag[x] ^= 1;

	}

	inline int findroot(int x){

		access(x);

		splay(x);

		while(ch[x][0]) x = ch[x][0];

		return x;

	}

	inline void split(int x, int y){

		mroot(x);

		access(y);

		splay(y);

	}

	inline void link(int x, int y){

		if(findroot(x) == findroot(y)) return;

		mroot(x);

		fa[x] = y;

	}

	inline void cut(int x, int y){

		split(x, y);

		ch[y][0] = fa[x] = 0;

		pushup(y);

	}

}qxz;

inline bool cmp(const Edge& a, const Edge& b){

	return a.w < b.w;

}

signed main(){

	N = read(), M = read(), Q = read();

	for(int i = 1; i <= M; ++i){

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

		if(e[i].u > e[i].v) swap(e[i].u, e[i].v);

	}

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

	for(int i = 1; i <= M; ++i){

		val[N+i] = e[i].w;

		E[make_pair(e[i].u,e[i].v)] = i;

	}

	for(int i = 1; i <= Q; ++i){

		K[i] = read(), X[i] = read(), Y[i] = read() ;

		if(X[i] > Y[i]) swap(X[i], Y[i]);

		if(K[i] == 2){

			q[i] = E[make_pair(X[i],Y[i])];

			used[q[i]] = 1;

		}

	}

	int x,y,cnt(0);

	for(int i = 1; i <= M && cnt < N-1; ++i){

		if(!used[i]){

			x = e[i].u, y = e[i].v;

			if(qxz.findroot(x) != qxz.findroot(y)){

				qxz.link(x, N+i);

				qxz.link(y, N+i);

				++cnt;

			}

		}

	}

	for(int i = Q; i; --i){

		x = X[i], y = Y[i];

		if(K[i] == 2){

			qxz.split(x, y);

			if(val[idmax[y]] > e[q[i]].w){

				int temp = idmax[y],t1 = e[temp-N].u, t2 = e[temp-N].v;

				qxz.cut(t1, temp), qxz.cut(t2, temp);

				qxz.link(x, N+q[i]), qxz.link(y, N+q[i]);

			}

		}

		else{

			qxz.split(x, y);

			ans[++top] = val[idmax[y]];

		}

	}

	while(top) printf("%lld\n", ans[top--]);

	return 0;

}

巴特西

☆ [WC2006] 水管局长「LCT动态维护最小生成树」

解题思路

反思

Code

最新文章

热门文章

巴特西

☆ [WC2006] 水管局长 「LCT动态维护最小生成树」

解题思路

反思

Code

最新文章

热门文章

☆ [WC2006] 水管局长「LCT动态维护最小生成树」