题解 P5243 【[USACO19FEB]Moorio Kart】

· · 题解

暴力能 A 的迷之题目。

题意可以理解为给你几棵小树，然后将这几颗小树连成一个环，使得环长 \ge Y ，求满足要求的树个数。

因为数据范围很小，考虑直接用 dfs 将每棵小树内的所有路径都统计出来。然后就变成了问给你几个集合，从这些集合中每个集合选择一个数，问和 \ge Y 的方案和。这是一个简单背包问题。求方案和可以顺便求出。

具体来说，设 dp[i][0/1] 表示 和为 i 的方案数/方案和， g[i][0/1] 表示当前小树内长度为 i 的路径数/长度和，则存在转移:

dp[i+j][0]\leftarrow dp[i][0]*g[j][0] dp[i+j][1]\leftarrow dp[i][0]*g[j][1] + dp[i][1]*g[j][0]

直接转移即可。

注意我们并不关注这个长度具体是多少，只关注它是否比 Y 大。并且长度大于等于 Y 的方案之后再怎么变都是满足要求的。因此可以将长度 \ge Y 的部分记在一起。还有个优化是可以直接从 X*k 开始转移。还有就是只转移 g 和 dp 有值的位置。

时间复杂度为 O(\sum n_i^2+\min\{Y,n_i^2\}(Y-XK))=O(NY\sqrt{Y}) ， n_i 为第 i 棵小树的点数。复杂度证明为考虑子树贡献，当 \forall i,Y=n_i^2时复杂度取得最大值。

代码:

#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;

namespace IO
{
    const uint32 Buffsize=1<<15,Output=1<<24;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
    {
        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
    }
    static char Out[Output],*nowps=Out;

    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)
    {
        x=0;static char ch;T f=1;
        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
        for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
        x*=f;
    }

    template<typename T>inline void write(T x,char ch='\n')
    {
        if(!x)*nowps++='0';
        if(x<0)*nowps++='-',x=-x;
        static uint32 sta[111],tp;
        for(tp=0;x;x/=10)sta[++tp]=x%10;
        for(;tp;*nowps++=sta[tp--]^48);
        *nowps++=ch;
    }
}
using namespace IO;

void file(void)
{
    FILE*DSD=freopen("water.in","r",stdin);
    FILE*CSC=freopen("water.out","w",stdout);
}

const int MAXN=1500+7,MAXY=2500+7,mod=1e9+7;

static int n,m;

static struct edge
{
    int v,w,nxt;
}p[MAXN<<1];

static int head[MAXN],e;

inline void add(int u,int v,int w)
{p[++e]=(edge){v,w,head[u]},head[u]=e;}

namespace DSU
{
    static int fa[MAXN];

    inline void clear(){Rep(i,1,n)fa[i]=i;}

    inline int Find(int u){return u==fa[u]?u:fa[u]=Find(fa[u]);}
}

static int X,Y;

inline void init()
{
    read(n),read(m),read(X),read(Y);
    DSU::clear();
    static int u,v,w;
    Rep(i,1,m)read(u),read(v),read(w)
        ,add(u,v,w),add(v,u,w),DSU::fa[DSU::Find(u)]=DSU::Find(v);
}

static int cn;

static int bel[MAXN],dst[MAXN][MAXY],sig[MAXN][MAXY];

void dftag(int u,int fr,int dir)
{
    bel[u]=dir;
    for(register int i=head[u];i;i=p[i].nxt)
    {
        int v=p[i].v;
        if(v^fr)dftag(v,u,dir);
    }
}

void dffix(int u,int fr,int len)
{
    if(fr)(sig[bel[u]][min(Y,len)]+=len)%=mod,++dst[bel[u]][min(Y,len)];
    for(register int i=head[u];i;i=p[i].nxt)
    {
        int v=p[i].v;
        if(v^fr)dffix(v,u,len+p[i].w);
    }
}

static int dp[MAXY][2],las[MAXY][2];

inline int fac(int u)
{
    register int sm=1;
    Rep(i,2,u)sm=(ll)sm*i%mod;
    return sm;
}

inline void solve()
{
    Rep(i,1,n)if(DSU::Find(i)==i)++cn,dftag(i,0,cn);
    Rep(i,1,n)dffix(i,0,0);
    static int st=min(Y,X*cn);
    dp[st][0]=1,dp[st][1]=X*cn;
    Rep(i,1,cn)
    {
        Rep(j,st,Y)las[j][0]=dp[j][0]
            ,las[j][1]=dp[j][1],dp[j][0]=dp[j][1]=0;
        Rep(j,0,Y)if(dst[i][j])Rep(k,st,Y)if(las[k][0])
        {
            dp[min(j+k,Y)][0]=(dp[min(j+k,Y)][0]+
                (ll)las[k][0]*dst[i][j])%mod;

            dp[min(j+k,Y)][1]=(dp[min(j+k,Y)][1]+
                (ll)las[k][0]*sig[i][j]+(ll)las[k][1]*dst[i][j])%mod;
        }
    }
    cout<<(ll)dp[Y][1]*fac(cn-1)%mod*((mod+1)/2)%mod<<endl;
}

int main()
{
    file();
    init();
    solve();
    return 0;
}