[BZOJ2238]Mst

题目大意：

给你一个\(n(n\le50000)\)个点，\(m(m\le10^5)\)条边的无向带权图。\(q(q\le10^5)\)次询问，每次询问去掉一条边后图能否连通，如果连通，求最小生成树。（询问互相独立）

思路：

首先求出最小生成树。对于非树边，去掉这条边对答案没有影响；对于树边，去掉这条边后就把原生成树分成两个不相交的连通块，新的最小生成树就是原树-该边边权+连接两个连通块的最小边。树链剖分+线段树维护即可。

时间复杂度\(\mathcal O((m+q)\log n)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

#include<climits>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=5e4+1,M=1e5+1;

int w[M];

struct Edge {

	int u,v,id;

	bool operator < (const Edge &rhs) const {

		return w[id]<w[rhs.id];

	}

};

Edge edge[M];

std::vector<int> e[N];

inline void add_edge(const int &u,const int &v) {

	e[u].push_back(v);

	e[v].push_back(u);

}

class DisjointSet {

	private:

		int anc[N],cnt;

		int find(const int &x) {

			return x==anc[x]?x:anc[x]=find(anc[x]);

		}

	public:

		void reset(const int &n) {

			cnt=n;

			for(register int i=1;i<=n;i++) anc[i]=i;

		}

		void merge(const int &x,const int &y) {

			anc[find(x)]=find(y);

			cnt--;

		}

		bool same(const int &x,const int &y) {

			return find(x)==find(y);

		}

		int size() const {

			return cnt;

		}

};

DisjointSet djs;

int dep[N],top[N],par[N],son[N],size[N],dfn[N];

void dfs(const int &x,const int &par) {

	size[x]=1;

	::par[x]=par;

	dep[x]=dep[par]+1;

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par) continue;

		dfs(y,x);

		size[x]+=size[y];

		if(size[y]>size[son[x]]) {

			son[x]=y;

		}

	}

}

void dfs(const int &x) {

	dfn[x]=++dfn[0];

	top[x]=x==son[par[x]]?top[par[x]]:x;

	if(son[x]!=0) dfs(son[x]);

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par[x]||y==son[x]) continue;

		dfs(y);

	}

}

int pos[M];

class SegmentTree {

	#define _left <<1

	#define _right <<1|1

	#define mid ((b+e)>>1)

	private:

		int val[N<<2];

	public:

		void build(const int &p,const int &b,const int &e) {

			val[p]=INT_MAX;

			if(b==e) return;

			build(p _left,b,mid);

			build(p _right,mid+1,e);

		}

		void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &v) {

			if(l>r||val[p]<=v) return;

			if(b==l&&e==r) {

				val[p]=std::min(val[p],v);

				return;

			}

			if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),v);

			if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,v);

		}

		int query(const int &p,const int &b,const int &e,const int &x) const {

			int ret=val[p];

			if(b==e) return ret;

			if(x<=mid) ret=std::min(ret,query(p _left,b,mid,x));

			if(x>mid) ret=std::min(ret,query(p _right,mid+1,e,x));

			return ret;

		}

	#undef _left

	#undef _right

	#undef mid

};

SegmentTree sgt;

inline int lca(int x,int y) {

	while(top[x]!=top[y]) {

		if(dep[top[x]]<dep[top[y]]) std::swap(x,y);

		x=par[top[x]];

	}

	if(dep[x]<dep[y]) std::swap(x,y);

	return y;

}

inline void modify(int x,int y,const int &w) {

	const int z=lca(x,y);

	while(top[x]!=top[y]) {

		if(dep[top[x]]<dep[top[y]]) std::swap(x,y);

		sgt.modify(1,1,dfn[0],dfn[top[x]]+(top[x]==z),dfn[x],w);

		x=par[top[x]];

	}

	if(dep[x]<dep[y]) std::swap(x,y);

	sgt.modify(1,1,dfn[0],dfn[y]+(y==z),dfn[x],w);

}

int main() {

	const int n=getint(),m=getint();

	for(register int i=1;i<=m;i++) {

		edge[i].u=getint();

		edge[i].v=getint();

		w[edge[i].id=i]=getint();

	}

	std::sort(&edge[1],&edge[m]+1);

	int sum=0;

	djs.reset(n);

	for(register int i=1;i<=m;i++) {

		const int &u=edge[i].u,&v=edge[i].v;

		if(djs.same(u,v)) continue;

		add_edge(u,v);

		djs.merge(u,v);

		sum+=w[edge[i].id];

	}

	if(djs.size()!=1) {

		for(register int q=getint();q;q--) {

			puts("Not connected");

		}

		return 0;

	}

	dfs(1,0);

	dfs(1);

	djs.reset(n);

	sgt.build(1,1,n);

	for(register int i=1;i<=m;i++) {

		int u=edge[i].u,v=edge[i].v;

		if(djs.same(u,v)) {

			modify(u,v,w[edge[i].id]);

			continue;

		}

		djs.merge(u,v);

		if(dep[u]<dep[v]) std::swap(u,v);

		pos[edge[i].id]=dfn[u];

	}

	const int q=getint();

	for(register int i=0;i<q;i++) {

		const int x=getint();

		if(pos[x]==0) {

			printf("%d\n",sum);

			continue;

		}

		const int tmp=sgt.query(1,1,n,pos[x]);

		if(tmp==INT_MAX) {

			puts("Not connected");

			continue;

		}

		printf("%d\n",sum-w[x]+tmp);

	}

	return 0;

}

巴特西

[BZOJ2238]Mst

[BZOJ2238]Mst

题目大意：

思路：

源代码：

最新文章

热门文章