2025_5_30 T4

· · 题解

省选对我们来讲还是太过棘手了些，所以来补CSP-S放松放松

大概有CF2300 左右 中位蓝

首先，题目给出一个DAG,第一联想为 topo 排序,再思考一下，不难发现，如果题目中没有 “炸水管” 的情况，问题非常简单，只需 topo 排序 转移，时间复杂度 O(n)，一个显然的暴力便有了

我们枚举那个“损坏”的边，每次都跑一遍上述的 topo ，时间复杂度 O(k \times n)，设 s_u 为点 u 的出边数，则

dp_v+=\frac{dp_u}{s_u}

想枚举损坏的边，肯定超时，我们考虑把所有可能坏掉的边的情况放在 topo 中一起转移

先思考一下，对于一个点 u，如果它的一条出边坏掉，会发生什么？还是设 s_u 为点 u 的出边数

假设坏水管连接的点为 v，其余的点为 t

对于 v ，从 u 流来的水因为水管爆炸的原因，固定为 0 ，所以流量由期望的 \frac{dp_u}{s_u} 变为 0

对于 t ， 流量则由原来的 \frac {dp_u}{s_u} 改为 \frac{dp_u}{s_u -1}

设 p=\frac{dp_u}{s_u}，q=\frac{dp_u}{s_u-1}

显然，影响是

dp_v-=p\times w \\ dp_t+=(q-p)\times w \\ (w 为此水管炸掉的概率)

掌握此式子，我们先求出在没有炸水管的情况下每个点的期望流量，再对于每个点，枚举它炸掉的出边即可转移，但对于菊花图，此做法会被卡到 O(n^2)

再思考一下，我们运用类似差分的思想，先利用 topo 求出没有炸水管时，每个点的流量 f_i，之后，对于每个点，我们枚举炸掉的出边

对于上文所述的 v ，流量因为水管爆炸而减小，故

g_v-=q\times w

同样，在此情况下，其他的点 t 会增加流量，我们可以理解为，向 u 注入了水，使其流向除开 v 的点，所以

g_u+=s_u\times (q-p)\times w

（p,q,w的定义同上） 最后，我们对所有的源点加上初始流量 1 ，直接 topo 即可

时间复杂度 O(n\times \log_2(V))（\log_2是求逆元的复杂度）

#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;
}