题解：AT_icpc2013spring_e 最小生成树

双倍经验

link1(gesp 9月 T2) 题库更新后会加入。

link2(Atcoder)

前言（废话）

本题解相对于其他另外两篇的题解更适合蒟蒻食用，有清楚的图解和 AC 代码示例。

本蒟蒻在 gesp 考试时遇到本题，因为没想到会考树剖导致写挂痛失近 500 rmb 。

(引用枚金牌大佬名言“不在考纲里就不算超纲”警示各位 oier 好好练题)。

思路

题目给定一个图，并且要求出删去某一条边后，图中的最小生成树。

有一种很

O(n^2)

的暴力做法，每次标记一条边不取，去求图中最小生成树。显然过不掉这题。

我们考虑优化每次删掉一条边如何快速求出一条“替代边”。我们先求出不删边的最小生成树，显然，对于那些不在最小生成树中的边，删掉也不会有什么影响。

那我们考虑对于不在树上的边该如何处理。用下面这三张图举例子：

这颗树是我们的最小生成树。

而这是一条不在树上的边（红色的）

对于这条“非树边”我们可以替换掉哪些边呢？显然是蓝色的边（如下）

由此我们知道了了在最小生成树上的边该如何解决。我们可以先求出原图中的最小生成树。并维护“非树边”的覆盖，我们可以通过树剖来维护每一条“树边”可替换的最短边。我们能在

O(\log^2 n)

的复杂度内添加一条“非树边”。然后对于每次替换我们可以在

O(\log n)

的复杂度内查询替换边。这样我们就做完这道题了。

坑点

树剖维护的是以这个点为子节点的边，在添加边时只能从 $u,v$ 添加到 $lca(u,v)$ 的子节点。（意思是 $lca(u,v)$ 并不会被添加）。
本蒟蒻认为树剖本身就具有许多坑点，需要多加小心。

AC代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int tag[4*N],mi[4*N];
int n;
void push_up(int op){
	mi[op]=min(mi[op*2],mi[op*2+1]);
	return;
}
void biuld(int l,int r,int op){
	tag[op]=2e9;
	if(l==r){
		mi[op]=2e9;
		return;
	}
	int mid=(l+r)/2;
	biuld(l,mid,op*2);
	biuld(mid+1,r,op*2+1);
	push_up(op);
	return;
} 
void add(int l,int r,int s,int t,int op,int k){
	if(s>=l&&t<=r){
		mi[op]=min(mi[op],k);
		tag[op]=min(tag[op],k);
		return;
	}
	int mid=(s+t)/2;
	if(tag[op]!=2e9){
		mi[op*2]=min(mi[op*2],tag[op]);
		mi[op*2+1]=min(mi[op*2+1],tag[op]);
		tag[op*2]=min(tag[op*2],tag[op]);
		tag[op*2+1]=min(tag[op*2+1],tag[op]);
		tag[op]=2e9;
	}
	if(l<=mid) add(l,r,s,mid,op*2,k);
	if(r>mid) add(l,r,mid+1,t,op*2+1,k);
	push_up(op);
	return;
}
int ask(int l,int r,int op,int p){
	if(l==r){
		return mi[op];
	}
	int mid=(l+r)/2;
	if(tag[op]!=2e9){
		mi[op*2]=min(mi[op*2],tag[op]);
		mi[op*2+1]=min(mi[op*2+1],tag[op]);
		tag[op*2]=min(tag[op*2],tag[op]);
		tag[op*2+1]=min(tag[op*2+1],tag[op]);
		tag[op]=2e9;
	}
	int res=2e9;
	if(p<=mid) res=min(res,ask(l,mid,op*2,p));
	else res=min(res,ask(mid+1,r,op*2+1,p));
	push_up(op);
	return res;
}
vector<int> g[N];
int hson[N],siz[N],top[N],dep[N],dfn[N],fa[N];
int new_ct;
int dfs1(int p,int f){
	fa[p]=f;
	dep[p]=dep[f]+1;
	siz[p]=1;
	int tmp=0;
	for(int i=0;i<g[p].size();i++){
		if(g[p][i]!=f){
			tmp=dfs1(g[p][i],p);
			siz[p]+=tmp;
			if(tmp>siz[hson[p]]){
				hson[p]=g[p][i];
			}
		}	
	} 
	return siz[p];
}
void dfs2(int p,int f,int tp){
	new_ct++;
	dfn[p]=new_ct;
	top[p]=tp;
	if(hson[p]) dfs2(hson[p],p,tp);
	for(int i=0;i<g[p].size();i++){
		if(g[p][i]!=f&&g[p][i]!=hson[p]){
			dfs2(g[p][i],p,g[p][i]);
		}
	}
	return;
}
void lca(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		add(dfn[top[u]],dfn[u],1,n,1,k);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	add(dfn[v]+1,dfn[u],1,n,1,k);//不加lca;
	return; 
}
int fat[N];
int find(int a){
	if(fat[a]==a) return a;
	return fat[a]=find(fat[a]);
}
struct side{
	int u,v,w;
	int op;
};
side s[N];
bool xz[N];
bool cmp(side a,side b){
	return a.w<b.w;
}
int ans[N];
int main(){
	int m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fat[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>s[i].u>>s[i].v>>s[i].w;
		s[i].op=i;
	} 
	sort(s+1,s+1+m,cmp);
	int u,v,w;
	int cnt=0;
	int tans=0;
	for(int i=1;i<=m;i++){
		u=s[i].u,v=s[i].v,w=s[i].w;
		int fu=find(u),fv=find(v);
		if(fu!=fv){
			fat[fu]=fat[fv];
			cnt++;
			tans+=w;
			xz[i]=1;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		if(cnt==n-1){
			break;
		}
	}
	dfs1(1,0);
	dfs2(1,0,1);
	biuld(1,n,1);
	for(int i=1;i<=m;i++){
		if(xz[i]!=1){
			ans[s[i].op]=tans;
			lca(s[i].u,s[i].v,s[i].w);
		}
	}
	int pt;
	int gx;
	for(int i=1;i<=m;i++){
		if(xz[i]==1){
			u=s[i].u,v=s[i].v,w=s[i].w;
			pt=dep[u]>dep[v]?u:v;
			gx=ask(1,n,1,dfn[pt]);
			if(gx==2e9){
				ans[s[i].op]=-1;
				continue;
			}
			ans[s[i].op]=tans-s[i].w+gx;
		}
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}

题解：AT_icpc2013spring_e 最小生成树

文章操作

双倍经验

前言（废话）

思路

坑点

AC代码

相关推荐

评论

题解：AT_icpc2013spring_e 最小生成树