专栏文章

2025_5_30 T4

EEvan_Leo_Azir
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip5ecgs
此快照首次捕获于
2025/12/03 06:26
3 个月前
此快照最后确认于
2025/12/03 06:26
3 个月前
查看原文
省选对我们来讲还是太过棘手了些，所以来补CSP-S放松放松
大概有CF2300 左右 中位蓝
首先，题目给出一个DAG,第一联想为 topotopo 排序,再思考一下，不难发现，如果题目中没有 “炸水管” 的情况，问题非常简单，只需 topotopo 排序 转移，时间复杂度 O(n)O(n)，一个显然的暴力便有了
我们枚举那个“损坏”的边，每次都跑一遍上述的 topotopo ，时间复杂度 O(k×n)O(k \times n)，设 sus_u 为点 uu 的出边数，则
dpv+=dpusudp_v+=\frac{dp_u}{s_u}
想枚举损坏的边，肯定超时，我们考虑把所有可能坏掉的边的情况放在 topotopo 中一起转移
先思考一下，对于一个点 uu，如果它的一条出边坏掉，会发生什么？还是设 sus_u 为点 uu 的出边数
假设坏水管连接的点为 vv，其余的点为 tt
对于 vv ，从 uu 流来的水因为水管爆炸的原因，固定为 00 ，所以流量由期望的 dpusu\frac{dp_u}{s_u} 变为 00
对于 tt ， 流量则由原来的 dpusu\frac {dp_u}{s_u} 改为 dpusu−1\frac{dp_u}{s_u -1}
设 p=dpusup=\frac{dp_u}{s_u}，q=dpusu−1q=\frac{dp_u}{s_u-1}
显然，影响是
dpv−=p×wdpt+=(q−p)×w(w为此水管炸掉的概率)dp_v-=p\times w \\ dp_t+=(q-p)\times w \\ (w 为此水管炸掉的概率)
掌握此式子，我们先求出在没有炸水管的情况下每个点的期望流量，再对于每个点，枚举它炸掉的出边即可转移，但对于菊花图，此做法会被卡到 O(n2)O(n^2)
再思考一下，我们运用类似差分的思想，先利用 topotopo 求出没有炸水管时，每个点的流量 fif_i，之后，对于每个点，我们枚举炸掉的出边
对于上文所述的 vv ，流量因为水管爆炸而减小，故
gv−=q×wg_v-=q\times w
同样，在此情况下，其他的点 tt 会增加流量，我们可以理解为，向 uu 注入了水，使其流向除开 vv 的点，所以
gu+=su×(q−p)×wg_u+=s_u\times (q-p)\times w
（p,q,wp,q,w的定义同上） 最后，我们对所有的源点加上初始流量 11 ，直接 topotopo 即可
时间复杂度 O(n×log⁡2(V))O(n\times \log_2(V))（log⁡2\log_2是求逆元的复杂度）
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,maxk=5e5+10,Mod=998244353;
int n,m,r,k,sumw,invs,cnte;
int head[maxn],in[maxn],in2[maxn],out[maxn],f[maxn],g[maxn];
struct EDGE{
	int v,nxt,w;
}e[maxk];
queue<int>Q;
int qpow(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod;
		y>>=1;
	}
	return ret;
}
void adde(int u,int v,int w)
{
	e[cnte]=(EDGE){v,head[u],w};
	head[u]=cnte++;
}
int add(int x,int y) {return x+y>=Mod?x+y-Mod:x+y;}
int fadd(int x,int y) {return x-y>=0?x-y:x-y+Mod;}
int read()
{
	int ret=0,w=1;char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
	return ret*w;
}
void inpu()
{
	n=read(),m=read(),r=read(),k=read();
	memset(head,-1,sizeof(head));
	for(int i=1,u,v,w;i<=k;i++)
	{
		out[u=read()]++,in[v=read()]++,sumw=add(sumw,w=read());
		adde(u,v,w);
	}
}
void pre()
{
	for(int i=1;i<=n;i++) in2[i]=in[i];
	for(int i=1;i<=m;i++) f[i]=g[i]=1;
	invs=qpow(sumw,Mod-2);
}
void topo()
{
	for(int i=1;i<=m;i++) Q.push(i);
	while(!Q.empty())
	{	
		int u=Q.front(),x=1ll*f[u]*qpow(out[u],Mod-2)%Mod;Q.pop();
		for(int i=head[u],to;i!=-1;i=e[i].nxt)
		{
			if(!(--in[to=e[i].v])) Q.push(to);
			f[to]=add(f[to],x);
		}
	}
}
void deal()
{
	for(int i=1;i<=n;i++) in[i]=in2[i];
	for(int u=1,p,q;u<=n-r;u++)
	{
		p=1ll*f[u]*qpow(out[u],Mod-2)%Mod,q=1ll*f[u]*qpow(out[u]-1,Mod-2)%Mod;
		for(int i=head[u],to,w;i!=-1;i=e[i].nxt)
		{
			to=e[i].v,w=1ll*e[i].w*invs%Mod;
			g[u]=add(g[u],1ll*out[u]*fadd(q,p)%Mod*w%Mod),g[to]=fadd(g[to],1ll*q*w%Mod);
		}
	}
	for(int i=1;i<=n;i++) f[i]=g[i];
}
void solve()
{
	inpu();
	pre();
	topo();
	deal();
	topo();
	for(int i=n-r+1;i<=n;i++) printf("%d ",f[i]);
}
int main()
{
	int t=1;
	while(t--) solve();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...