题解：P8950 [YsOI2022] 道路修建

好题，补一下题解。

注意到对于

k=1

的情况不弱于最小树形图的板子。

回顾一下朱刘算法的过程：我们维护了一个内向树森林，每次取出一个没有出度的根节点 $u$ ，找到它的最小出边 $v$ ，则有两种情况：

$u$ 和 $v$ 不连通，直接连起来即可。

$u,v$ 本来就联通，此时 $v\to u$ 这一条链上的所有点就在一个环上，此时我们可以把这个环缩成点。

但是缩点之后这个环内多了一条边。考虑环内的点 $u$ ，设它延伸出去的边长度为 $d$ ，则如果别的边从 $u$ 连出去，则需要断开 $d$ 这条边。所以我们需要枚举 $u$ 的所有边，并且将其长度减去 $d$ ，这样就正确了。

用带懒标记的可并堆去快速找到每个点的最小出边，复杂度为 $O(n\log n)$ 。

考虑拆贡献，计算每条边被包含的次数。

设我们现在考虑到

u\to v

这条边。记

S_u

表示

u

节点包含的原图中的点的集合，则如果没有点在

S_u

内，则

S_u

中的点就会从这条边中走出去，贡献系数为

\dfrac {\binom{n-|S_u|}{k} }{\binom{n}{k}}

。

判断无解也是简单的：如果最终发现有一个根节点

u

满足

|S_u|+k\le n

，则我们可以把这

k

个节点全部扔到

S_u

的外面，这样就寄了。

CPP

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace io{

template<typename T>
inline void gi(T &x)
{
	x=0;char ch=getchar();
	while(ch<'0'||'9'<ch) ch=getchar();
	while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
template<typename T>
void print(T x)
{
	if(x<=9) return putchar(x+'0'),void();
	print(x/10),putchar(x%10+'0');
}

}using io::gi;using io::print;


const int N=5e5+9;
const int mod=998244353;

int fac[N],inv[N],ifac[N];
void ycl(int lim=2e5)
{
	fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=ifac[1]=1;
	for(int i=2;i<=lim;i++)
	{
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
	}
}
int C(int x,int y){return x>=y&&y>=0?1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod:0;}
int invC(int x,int y){return x>=y&&y>=0?1ll*ifac[x]*fac[y]%mod*fac[x-y]%mod:0;}

pii val[N];
int siz[N],son[N][2],tag[N],dep[N],tcnt=0;
int new_node(pii x)
{
	int u=++tcnt;
	siz[u]=1;tag[u]=son[u][0]=son[u][1]=0;
	val[u]=x;
	return u;
}
void Add(int u,int x){if(u) val[u].first+=x,tag[u]+=x;}
void pushdown(int u){if(tag[u]) Add(son[u][0],tag[u]),Add(son[u][1],tag[u]),tag[u]=0;}
void pushup(int u){siz[u]=siz[son[u][0]]+siz[son[u][1]]+1,dep[u]=dep[son[u][1]]+1;}
int Merge(int u,int v)
{
	if(!u||!v) return u+v;
	pushdown(u),pushdown(v);
	if(val[u]>val[v]) swap(u,v);
	son[u][1]=Merge(son[u][1],v);
	if(dep[son[u][0]]<dep[son[u][1]]) swap(son[u][0],son[u][1]);
	return pushup(u),u;
}
void pop(int &rt){pushdown(rt);rt=Merge(son[rt][0],son[rt][1]);}

int n,m,K;

int rt[N];

int nxt[N],len[N],tp[N];
int siz1[N];
int gettp(int x){return tp[x]==x?x:tp[x]=gettp(tp[x]);}

int bcj[N];
int getfa(int x){return bcj[x]==x?x:bcj[x]=getfa(bcj[x]);}

signed main()
{
	ycl();
	gi(n),gi(m),gi(K);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		gi(u),gi(v),gi(w);
		if(u!=v)
		rt[u]=Merge(rt[u],new_node(make_pair(w,v)));
	}
	for(int i=1;i<=n;i++) bcj[i]=tp[i]=i;
	for(int i=1;i<=n;i++) siz1[i]=1;
	int ans=0;
	for(int u=1;u<=n;u++)
	{
		while(siz[rt[u]])
		{
			int v=val[rt[u]].second;
			if(gettp(u)==gettp(v)) {pop(rt[u]);continue;}
			(ans+=1ll*C(n-siz1[gettp(u)],K)*(val[rt[u]].first%mod+mod)%mod)%=mod;
			if(getfa(u)==getfa(v))
			{
				int uu=gettp(v),d=val[rt[u]].first;
				pop(rt[u]);
				Add(rt[u],-d);
				while(uu!=u)
				{
					Add(rt[uu],-len[uu]);
					rt[u]=Merge(rt[u],rt[uu]);
					uu=gettp(nxt[uu]);
				}
				uu=gettp(v);
				while(uu!=u)
				{
					siz1[u]+=siz1[uu];
					bcj[uu]=tp[uu]=u;
					uu=gettp(nxt[uu]);
				}
			}
			else
			{
				nxt[u]=gettp(v),len[u]=val[rt[u]].first;
				bcj[u]=v;
				break;
			}
		}
		if(!siz[rt[u]])
		{
			if(siz1[u]+K<=n) return puts("-1"),0;
			continue;
		}
	}
	print(1ll*ans*invC(n,K)%mod);
}

题解：P8950 [YsOI2022] 道路修建

文章操作

相关推荐

评论

题解：P8950 [YsOI2022] 道路修建