题解
即O(N^2)暴力统计出每个森林的路径,从ctgn个集合中各选出一个数,使得长度>=Y的方案数.
用背包统计.具体实现:
\(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放到一起,并且可以从X*ctgn就开始转移
细节详见代码
#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)
{
//dst[i][j]:预处理第i颗森林长度为j的路径条数; sig[i][j]:路径长度之和
//细节处理:不是根节点才能算路径方案数
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);//取min的唯一目的就是把超过Y的放到Y里面,仅此而已
dp[st][0]=1,dp[st][1]=X*cn;//初始状态有1种方案,总长度为所有的X边
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;//先存起来
//注意有0边
Rep(j,0,Y)if(dst[i][j])Rep(k,st,Y)if(las[k][0])//本来是倒序枚举的背包,但是上限可能会超过Y不好控制,就顺序枚举对j+k和Y取min来更新
{
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;//最后考虑cn个联通块之间连接的顺序排列
}
int main()
{
//file();
init();
solve();
return 0;
}