【题解】[牛客OI周赛4-提高组]A.K小生成树 枚举+前缀和+剪枝

题目链接

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10,Q=1e4+10,INF=0x3f3f3f3f;
int n,m,a[N],fa[21],l,r,f1,f2,ans,tot,flag,q,askl[Q],askr[Q],minl=INF,maxr=-INF;
struct Edge{
	int u,v,w;
}e[26];
inline int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	    scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)//离线读入 
	{
		scanf("%d%d",&askl[i],&askr[i]);
		minl=min(askl[i],minl);maxr=max(askr[i],maxr);
	}
	for(int i=1;i<(1<<m);i++)//枚举边集 
	{
		ans=i;tot=0;flag=1;
		while(ans)
		{
			ans&=(ans-1);tot++;
		}
		if(tot!=n-1)flag=0;//如果不为n-1条边，剪枝 
		if(flag)
		{
			ans=0;
			for(int j=1;j<=n;j++)
			    fa[j]=j;
			for(int j=1;j<=m;j++)
			    if(i&(1<<(j-1)))
			    {
			    	ans+=e[j].w;f1=Find(e[j].u);f2=Find(e[j].v);
			    	if(f1==f2){flag=0;break;}//如果成环，剪枝 
					else fa[f1]=f2; 
				}
			if(flag&&ans>=minl&&ans<=maxr)a[ans-minl+1]++;//只记录[minl,maxr]，优化前缀和数组大小 
		}
	}
	for(int i=1;i<=maxr-minl+1;i++)a[i]+=a[i-1];//变成前缀和
	for(int i=1;i<=q;i++)
	    printf("%d\n",a[askr[i]-minl+1]-a[askl[i]-minl]);
	return 0; 
}

总结

因为边数小，可以直接枚举边集，离线读入和前缀和处理以及区间偏移是关键。