题解：P14415 [JOISC 2015] 遗产继承 / Inheritance

闲话

~~什么日本神题~~

被大手子拉过来刷题了。

正文

看了一眼，简化一下题意。

形式化题面

给定

n

个点，

m

条带权无向边，要求删去

k

轮边，满足删去的边不成环且边权最大，无满足则不删。最后输出每条边在第几轮删去，若未删去则输出 0。

暴力

直接跑

k

遍最大生成树，时间复杂度为

\Theta(k\times m\times \log _2m\times \alpha(n))

，直接炸缸。

正解

~~根据大手子の情报~~根据直觉，删边的顺序存在单调性。

具体而言，假如一条边在第

i

轮被删去，则它不可能会在之后被删，因为这对于第

i

轮不优；它同样不会在之前被删，因为这对于之前的轮数不优。

由此我们考虑维护

k

个并查集，其中第

i

个维护第

i

轮所选的边。对于第

i

条边，我们依据单调性进行二分，求出该边最早在哪个并查集里满足不会构成环，二分结束后将第

i

条边加入所属的并查集。

单次二分时间复杂度为

\Theta( \log _2k \times \alpha(n))

，总共进行

m

轮，再加上原先的排序，总复杂度为

\Theta(m\times \log _2k \times \alpha(n)+m \log _2m)

，稳稳通过。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10;
struct node{
	int chos,u,v,w,id;
	friend bool operator <(const node &a,const node &b){
		if(a.chos^b.chos) return a.chos<b.chos;
		if(a.w^b.w) return a.w>b.w;
		if(a.id^b.id) return a.id<b.id;
		if(a.u^b.u) return a.u<b.u;
		return a.v<b.v;
	}
};
struct DSU{
	V<int>fa;
	DSU(int _n):fa(_n+1){iota(fa.begin(),fa.end(),0);}
	int fin(int x){
		while(x^fa[x])x=fa[x]=fa[fa[x]];
		return x;
	}
	bool is_(int u,int v){
		return fin(u)==fin(v);
	}
	void merge(int u,int v){
		if(is_(u,v)) return;
		u=fin(u),v=fin(v);
		fa[u]=v;
	}
};
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m,k;cin>>n>>m>>k;
	V<DSU> dsu(k+1,DSU(n));
	V<node>e(m+1);
	FOR(i,1,m){
		cin>>e[i].u>>e[i].v>>e[i].w;e[i].chos=0;e[i].id=i;
	}
	V<int>ans(m+1,0);
	sort(e.begin()+1,e.end());
	auto check=[&](int edge,int x){
		return dsu[x].is_(e[edge].u,e[edge].v);
	};
	FOR(i,1,m){
		int l=1,r=k,res=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(check(i,mid)){
				l=mid+1;
			}else{
				res=mid;
				r=mid-1;
			}
		}
		if(res){
			ans[e[i].id]=res;
			dsu[res].merge(e[i].u,e[i].v);
		}
	}
	FOR(i,1,m) cout<<ans[i]<<"\n";
	return 0;
}

题解：P14415 [JOISC 2015] 遗产继承 / Inheritance

文章操作

闲话

正文

形式化题面

暴力

正解

代码

相关推荐

评论

题解：P14415 [JOISC 2015] 遗产继承 / Inheritance