The 2020 ICPC Asia Yinchuan Regional Programming Contest D. Farm(LCT维护最小生成树/可撤销并查集)

题目

n(n<=1e5)个点，m(m<=5e5)条边，第i条边的代价是ci(1<=ci<=1e3)

q(0<=q<=16)个限制，第i个限制给出ui,vi，要求这两条边至少选一条，

求n个点连通的最小代价，图可能有自环、重边

思路来源

乱搞AC

题解

很暴力的做法，首先求最小生成树，然后用LCT维护最小生成树

由于维护的是边权，而LCT是查点权的，

所以新开一个点w，u连w，w连v，点权=边权

对于自环边直接忽略，然后考虑2的q次方枚举限制取哪个，

将q条边加到树上时，由于已经是一棵树了，再加一条边会成环

所以每次加(u,v)之前先找到树上最大的边，将代价减掉，再将当前边加上，

也就是起到边替换的效果

为了避免q条边内部后面的边将前面的边替换掉，

所以在把这q条边往树上加的时候，先用变量记好对应的代价变化，

而加到树上的代价为0，防止被取代掉，枚举下一个方案时将当前方案回滚即可

2的q次方，每次q条边，暴力枚举是的，

link和cut操作较多，常数较大，无法通过，

将其改为dfs，复杂度，就可以通过了，

因为dfs树只有2n条边，向下搜的时候link A&cut B，向上搜的时候cut A&link B

心得

之前wa了一天，也没能查出来原因/反例是什么

之前的断边时，是把要断的点splay到根，再切断两个son(w和u、w和v)的联系

后来改成标准的cut操作后，就可以通过了

代码

#include <bits/stdc++.h>
// #include <iostream>
// #include <cstdio>
using namespace std;

constexpr int N = 6e5+100,M=5e5+10,Q=17,INF=0x3f3f3f3f;
struct LinkCutTree {
	bool rev[N];
	int fa[N],ch[N][2];
	int val[N],mx[N];

	#define ls(x) (ch[x][0])
	#define rs(x) (ch[x][1])
	#define dir(x) (x == ch[fa[x]][1])
	#define IsRoot(x) (x != ch[fa[x]][0] && x != ch[fa[x]][1])

	inline void PushUp(int x) {
		mx[x] = x;
		if(ls(x) && val[mx[ls(x)]] > val[mx[x]]) mx[x] = mx[ls(x)];
		if(rs(x) && val[mx[rs(x)]] > val[mx[x]]) mx[x] = mx[rs(x)];
	}

	inline void PushDown(int x) {
		if(rev[x]) {
			if(ls(x)) std::swap(ls(ls(x)),rs(ls(x))),rev[ls(x)] ^= 1;
			if(rs(x)) std::swap(ls(rs(x)),rs(rs(x))),rev[rs(x)] ^= 1;
			rev[x] = 0;
		}
	}

	void update(int x) {
		if(!IsRoot(x)) update(fa[x]);
		PushDown(x);
	}

	inline void rotate(int x) {
		int y = fa[x],z = fa[y],d = dir(x),w = ch[x][d ^ 1];
		if(!IsRoot(y)) ch[z][dir(y)] = x;
		ch[y][d] = w,ch[x][d ^ 1] = y;
		fa[y] = x,fa[x] = z;
		if(w) fa[w] = y;
		PushUp(y);
	}

	inline void splay(int x) {
		update(x);
		while(!IsRoot(x)) {
			int y = fa[x],z = fa[y];
			if(!IsRoot(y))
				rotate((ls(y) == x) ^ (ls(z) == y) ? x : y);
			rotate(x);
		}
		PushUp(x);
	}

	inline void access(int x) {
		for(int p = 0;x;p = x,x = fa[x])
			splay(x),rs(x) = p,PushUp(x);
	}

	inline void MakeRoot(int x) {
		access(x),splay(x);
		std::swap(ls(x),rs(x)),rev[x] ^= 1;
	}

	inline int FindRoot(int x) {
		access(x),splay(x);
		while(ls(x)) PushDown(x),x = ls(x);
		splay(x);
		return x;
	}

	inline void split(int x,int y) {
		MakeRoot(x),access(y),splay(y);
	}

	inline void link(int x,int y) {
		MakeRoot(x); 
		if(FindRoot(y)!=x)fa[x] = y;
	}

	inline void cut(int x,int y) {
		MakeRoot(x);
		if(FindRoot(y)==x && fa[y]==x && !ls(y)){
			fa[y]=rs(x)=0;
			PushUp(x);
		}
	}
}T;
int n,m,q,ecnt,res,ans=INF,del[Q];
array<int,3>a[M];
array<int,2>lim[Q],to[N];
int used[M];
void dfs(int x){
	if(x==q){
		ans=min(ans,res);
		return;
	}
	int cur=n+m+1+x;
	for(int i=0;i<2;++i){
		int id=lim[x][i],ep=-1;
		int u=a[id][0],v=a[id][1],w=a[id][2];
		bool add=0,del=0;
		if(!used[id]){
			add=1;
			used[id]++;
			res+=w;
			if(u!=v){
				T.split(u,v);
				ep = T.mx[v];
				if(T.val[ep]){
					del=1;
					T.val[cur]=0;
					T.cut(ep,to[ep][0]);
					T.cut(ep,to[ep][1]);
					T.link(cur,u);
					T.link(cur,v);
					res-=T.val[ep];
				}
			}
		}
		dfs(x+1);
		if(add){
			used[id]--;
			res-=w;	
			if(del){
				T.cut(cur,u);
				T.cut(cur,v);
				T.link(ep,to[ep][0]);
				T.link(ep,to[ep][1]);
				res+=T.val[ep];
			}
		}
	}
}
int sol(){
	scanf("%d",&q);
	for(int i=0;i<q;++i){
		scanf("%d%d",&lim[i][0],&lim[i][1]);
	}
	if(ecnt<n-1)return -1;
	dfs(0);
	return ans;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;++i) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		a[i]={u,v,w};
		if(u == v) continue;
		T.val[i + n] = w;
		to[i+n]={0,0};
		T.MakeRoot(u);
		if(u != T.FindRoot(v)) {
			to[i+n]={u,v};
			T.link(i + n,u),T.link(i + n,v);
			++ecnt;
			res += w;
		}
		else {
			T.split(u,v);
			int ep = T.mx[v];
			if(w < T.val[ep]) {
				T.cut(ep,to[ep][0]);
				T.cut(ep,to[ep][1]);
				T.link(i + n,u);
				T.link(i + n,v);
				to[i+n]={u,v};
				res -= T.val[ep];
				res += w;
			}
		}
	}
	printf("%d\n",sol());
	return 0;
}

/*
3 3
1 2 3
2 3 4
3 1 1 
2
1 2
1 3

3 3
1 2 3
2 3 4
3 1 1 
2
1 2
2 1

*/