愿题解

闲扯前言

一篇题解可能需要一张头图。

所以这篇题解讲的是 @GM_Joanna_ 的做法。

stO Orz

另外我完全没有责怪/诋毁 @ღꦿ࿐ 的意思，本篇题解仅为分享做法，出题人看到了还请海涵。

传送门

题解

首先容易发现这个问题在图上做和在这张图的最小生成树上做是等价的，具体来说，两个点是否连通只和它们之间所有路径中最大值最小的路径有关，这是一个瓶颈路问题，我们考虑用 Kruskal 的思想解决。

有一个转化，我们发现原题里面的 $h$ 是水位高于或等于这个值就必须相同，这非常不好处理，我们考虑设 $H=h-1$ 表示水位小于或等于这个值，这条边两侧就是两个独立的问题。

考虑跑 Kruskal 的过程，容易发现在任意时刻，某个集合内的水位假如高于其中最小生成树上边权最大的边（即 Kruskal 过程中对这个集合连的最后一条边），那么这整个集合内水位必定相同。容易想到按跑 Kruskal 的过程为 DP 的“阶段”做 DP。

设 $f_{i,j}$ 表示 Kruskal 进行到第 $i$ 步，集合 $j$ 内的方案数，$stg_i$ 表示集合 $i$ 的最小生成树上边权最大的边。设这一步合并 $u,v$ 两个集合为 $w$（这里不考虑 $u,v$ 本来就在一个集合的情况），加的这条边边权为 $H$，易得能得到转移方程：

$$ \begin{cases} f_{i,j}=f_{i-1,j} &j\ne u,v \\ f_{i,w}=(f_{i-1,u}+H-stg_{u})\times (f_{i-1,v}+H-stg_{v}) \end{cases} $$

如何理解呢？首先第一种情况显然，因为这条边不会对他们有影响。

对于第二种情况，首先两边水位在小于等于 $H$ 的时候是独立的问题，适用乘法原理。两边分别的方案数就是之前的方案数加上两个集合水位整体取 $stg_{u/v}+1\sim H$ 的方案，加起来相乘即可。

然后显然 $stg_w=H$，因为前面连的所有边边权都小于等于 $H$。

然后考虑如何统计答案，在 DP 的合并过程中，假如结点 $1$ 不在 $u,v$ 中，那么这里就不用管它，然后假如 $1$ 在集合 $u$ 里，那么它能取到的水位就是从 $stg_{u/v}$ 到 $H$ 的等差数列，然后根据乘法原理在这一步就会有 $(f_{i,v}+H-stg_v)$ 种不同的情况取到等差数列里面的每一位，做一个等差数列求和即可。

另外显然这个 DP 的第一维可以压掉。

考虑最终如何统计答案。首先每个集合只统计了水位在 $0 \sim stg_i$ 的情况，$f_i$ 再加上 $d-stg_i$ 即可，对答案同理加上一个等差数列。注意到最后整张图可能不连通，而每个连通块的情况是独立的，还是用乘法原理，故最终答案为 $ans\times \prod_{1 \notin i}f_i$（这里的 $ans,f$ 均是最终处理过的）。

code

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=1e5+5,inf=0x3f3f3f3f,mod=998244353;
i64 n,m,d,ans;
i64 fa[N],pl[N],stg[N];
i64 getfa(i64 x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
struct edge{
    i64 u,v,h;
}e[N*2];
bool cmp(edge a,edge b){
    return a.h<b.h;
}
i64 inv2=(mod-mod/2)%mod;
signed main(){
    n=read();m=read();d=read();
    forup(i,1,n){
        fa[i]=i;
        pl[i]=0;
    }
    forup(i,1,m){
        e[i].u=read();e[i].v=read();e[i].h=read()-1;
    }
    sort(e+1,e+m+1,cmp);
    forup(i,1,m){
        i64 u=e[i].u,v=e[i].v,dpt=e[i].h;
        i64 f1=getfa(1),fu=getfa(u),fv=getfa(v);
        if(fu==fv) continue;
        if(f1==fu){
            ans=(ans+(stg[fu]+1+dpt)*(dpt-stg[fu]+mod)%mod*inv2%mod)%mod*(pl[fv]+dpt-stg[fv]+mod)%mod;
        }
        if(f1==fv){
            ans=(ans+(stg[fv]+1+dpt)*(dpt-stg[fv]+mod)%mod*inv2%mod)%mod*(pl[fu]+dpt-stg[fu]+mod)%mod;
        }
        fa[fu]=fv;
        pl[fv]=(pl[fu]+dpt-stg[fu]+mod)*(pl[fv]+dpt-stg[fv]+mod)%mod;
        stg[fv]=dpt; 
    }
    i64 f1=getfa(1);
    ans=(ans+(stg[f1]+1+d)*(d-stg[f1]+mod)%mod*inv2%mod)%mod;
    forup(i,1,n){
        if(getfa(i)==i&&getfa(i)!=f1){
            pl[i]+=(d-stg[i]);
            (ans*=pl[i])%=mod;
        }
    }
    printf("%lld",ans);
}

愿 题解

闲扯 前言

题解

code

Comments

愿题解

闲扯前言