题面不放

这是道好题 一开始还以为是\rm{Matrix Tree}定理,后来发现不是QAQ

其实暴搜可过

先一遍Kruskal,顺便把权值相等的边们分到一个块里面,随便怎么实现都行 记录一下每个块有多少边在MST中出现过

然后重置一下并查集,枚举块,每个块跑DFS选哪些边(注意连通性,如果这条边加入成环就不能选,这很显然qwq),答案是所有块的方案数的乘积。

这里用了一个性质就是不同的MST中边权相等的边出现次数相等,证明?

开始时,每个点单独构成一个集合。

首先只考虑权值最小的边,将它们全部添加进图中,并去掉环,由于是全部尝试添加,那么只要是用这种权值的边能够连通的点,最终就一定能在一个集合中。

那么不管添加的是哪些边,最终形成的集合数都是一定的,且集合的划分情况一定相同。那么真正添加的边数也是相同的。因为每添加一条边集合的数目便减少1.

那么权值第二小的边呢?我们将之间得到的集合每个集合都缩为一个点,那么权值第二小的边就变成了当前权值最小的边,也有上述的结论。

因此每个阶段,添加的边数都是相同的。我们以权值划分阶段,那么也就意味着某种权值的边的数目是完全相同的。

上文不是我写的。引用一下。

然后就能愉快的切掉这个水题。

 

点击图片跳转原题

 

 

 

 

 

哦,还有,这段代码BZOJ编译会CE,不知道为什么她就是不支持C++11   [摊手]

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#define mo 31011
#define ll long long
using namespace std;

struct ed { int fr,to,w; }edge[100010]={0};
struct gr { int w,cnt; } gro[100010]={0};
struct blocks { int lx,rx,num; } blk[100010]={0};
int nodenum,edgenum,mstnum=0,blkm=0,nblk,ans=1,ansx;
int fa[100010]={0};

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline int findx(int e) { if (fa[e]!=e) return findx(fa[e]); return fa[e]; }

inline void dfs(int npos,int used)
{
	if (npos==blk[nblk].rx+1)
	{
		if (used==blk[nblk].num) ansx++;
		return;
	}
	int u=findx(edge[npos].fr),v=findx(edge[npos].to);
	if (u!=v)
	{
		fa[u]=v;
		dfs(npos+1,used+1);
		fa[u]=u; fa[v]=v;
	}
	dfs(npos+1,used);
}

int main()
{
	readx(nodenum); readx(edgenum);
	for (int i=1;i<=edgenum;i++) { readx(edge[i].fr); readx(edge[i].to); readx(edge[i].w); }
	for (int i=1;i<=nodenum;i++) fa[i]=i;
	sort(edge+1,edge+edgenum+1,[](ed a,ed b){return a.w<b.w;});
	
	for (int i=1;i<=edgenum;i++)
	{
		if (edge[i].w!=edge[i-1].w) { blk[blkm].rx=i-1; blk[++blkm].lx=i; }
		if (findx(edge[i].fr)!=findx(edge[i].to))
		{
			fa[findx(edge[i].fr)]=findx(edge[i].to); mstnum++;
			blk[blkm].num++;
		}
	}
	if (mstnum<nodenum-1) { printf("0\n"); return 0; }
	
	blk[blkm].rx=edgenum;
	for (int i=1;i<=nodenum;i++) fa[i]=i;
	
	for (int i=1;i<=blkm;i++)
	{
		nblk=i; ansx=0;
		dfs(blk[i].lx,0); ans=(ans*ansx)%mo;
		for (int j=blk[i].lx;j<=blk[i].rx;j++) if (findx(edge[j].fr)!=findx(edge[j].to)) 
			fa[findx(edge[j].fr)]=findx(edge[j].to);
	}
	printf("%d\n",ans);
	return 0;
}

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.