题目描述

Bessie 和 Farmer John 喜欢山羊卡丁车比赛。这个比赛非常类似于其他人喜欢的卡丁车比赛，除了卡丁车是由山羊拉动，以及赛道是由农田组成。农田由 N 个草地和 M 条道路组成，每条道路都连接着两个草地。

定义农场是两个或更多草地的一个集合，同一农场中的每个草地都可以沿着一系列唯一的道路到达农场中其他任意一个草地。

整个农田可能由多个农场组成，假设图中有 K 个农场。Bessie 希望通过添加长度为 X 的 K 条道路，连接所有 K 个农场来制作山羊卡丁车赛道。每个农场只应访问一次，并且每个农场内必须至少穿过一条道路。

为了让选手们对赛道更有兴趣，赛道的长度至少应该为 Y 。Bessie 希望知道所有这些有趣赛道的赛道长度总和。如果一个赛道中有两个农场直接相连，但另外一个赛道中这两个农场没有直接相连的话，这两个赛道就是不同的。

1≤N≤1500,1≤M≤N?1,0≤X,Y≤2500

题解

直接dp是n^3的，也许能过，并且显然可以直接卷积

题解做法：假设块的大小为K，若K^2<=Y则一个个加，否则一起加

这样时间是min(K^{2,Y)的，最坏情况下K=√n，时间复杂度O(Y}2√n)

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%1000000007
#define sqr(x) ((x)*(x))
#define mod 1000000007
#define ll long long
#define file
using namespace std;

int a[3001][3],F[2501][2],ls[1501],d[1501],bg[1501],ed[1501],dis[1501][1501],n,m,i,j,k,l,len,x,y,tot;
ll f[1501][2501][2],g[1501][2],ans,g1,g2;
bool bz[1501];

void New(int x,int y,int z) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;a[len][2]=z;}
void dfs(int Fa,int t)
{
	int i;
	d[++j]=t;
	bz[t]=1;
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa && !bz[a[i][0]])
	dfs(t,a[i][0]);
}
void Dfs(int Fa,int t,int Dis)
{
	int i;
	dis[l][t]=Dis;
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa)
	Dfs(t,a[i][0],Dis+a[i][2]);
}

int main()
{
	freopen("mooriokart.in","r",stdin);
	#ifdef file
	freopen("mooriokart.out","w",stdout);
	#endif
	
	scanf("%d%d%d%d",&n,&m,&x,&y);y=max(y-(n-m)*x,0);
	fo(i,1,m) scanf("%d%d%d",&j,&k,&l),New(j,k,l),New(k,j,l);
	
	j=0;
	fo(i,1,n) if (!bz[i]) ++tot,bg[tot]=j+1,dfs(0,i),ed[tot]=j;
	fo(l,1,n) Dfs(0,l,0);
	
	fo(i,1,ed[1]-1)
	{
		fo(j,i+1,ed[1])
		if (dis[d[i]][d[j]]<y)
		add(f[1][dis[d[i]][d[j]]][0],dis[d[i]][d[j]]),++f[1][dis[d[i]][d[j]]][1];
		else
		add(g[1][0],dis[d[i]][d[j]]),++g[1][1];
	}
	
	fo(i,2,tot)
	{
		if (sqr(ed[i]-bg[i]+1)<=y)
		{
			fo(j,0,y-1)
			if (f[i-1][j][0] || f[i-1][j][1])
			{
				fo(k,bg[i],ed[i]-1)
				{
					fo(l,k+1,ed[i])
					if (j+dis[d[k]][d[l]]<y)
					add(f[i][j+dis[d[k]][d[l]]][0],f[i-1][j][0]*2+f[i-1][j][1]*2*dis[d[k]][d[l]]),add(f[i][j+dis[d[k]][d[l]]][1],f[i-1][j][1]*2);
					else
					add(g[i][0],f[i-1][j][0]*2+f[i-1][j][1]*2*dis[d[k]][d[l]]),add(g[i][1],f[i-1][j][1]*2);
				}
			}
			fo(k,bg[i],ed[i]-1)
			{
				fo(l,k+1,ed[i])
				add(g[i][0],g[i-1][0]*2+g[i-1][1]*2*dis[d[k]][d[l]]),add(g[i][1],g[i-1][1]*2);
			}
		}
		else
		{
			memset(F,0,sizeof(F));
			g1=g2=0;
			fo(j,bg[i],ed[i]-1)
			{
				fo(k,j+1,ed[i])
				if (dis[d[j]][d[k]]<y)
				add(F[dis[d[j]][d[k]]][0],dis[d[j]][d[k]]*2),F[dis[d[j]][d[k]]][1]+=2;
				else
				add(g1,dis[d[j]][d[k]]*2),g2+=2;
			}
			
			fo(j,0,y-1)
			if (f[i-1][j][0] || f[i-1][j][1])
			{
				fo(k,0,y-1)
				{
					if (j+k<y)
					add(f[i][j+k][0],f[i-1][j][0]*F[k][1]+f[i-1][j][1]*F[k][0]),add(f[i][j+k][1],f[i-1][j][1]*F[k][1]);
					else
					add(g[i][0],f[i-1][j][0]*F[k][1]+f[i-1][j][1]*F[k][0]),add(g[i][1],f[i-1][j][1]*F[k][1]);
				}
				add(g[i][0],f[i-1][j][0]*g2+f[i-1][j][1]*g1),add(g[i][1],f[i-1][j][1]*g2);
			}
			fo(k,0,y-1)
			add(g[i][0],g[i-1][0]*F[k][1]+g[i-1][1]*F[k][0]),add(g[i][1],g[i-1][1]*F[k][1]);
			add(g[i][0],g[i-1][0]*g2+g[i-1][1]*g1),add(g[i][1],g[i-1][1]*g2);
		}
	}
	
	ans=(g[tot][0]+g[tot][1]*(n-m)%mod*x)%mod;
	fo(i,1,n-m-1)
	ans=ans*i%mod;
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

6613. Moorio Kart

原文：https://www.cnblogs.com/gmh77/p/12862498.html