BZOJ1016 [JSOI2008]最小生成树计数

题面

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对$31011$的模就可以了。(具有相同权值的边不会超过10条)

思路

这题有点ex啊,不知道矩阵树定理或者最小生成树两个特殊性质就gg了。(显然我gg了)

最小生成树有两个特殊性质

1.如果一张图存在多个最小生成树,他们边权的组成是一样的,比如一棵最小生成树的边权组成是$(1,1,2,2,3)$那么其它的边权组成也是$(1,1,2,2,3)$。

2.不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的

那么我们就可以从小到大加边,然后把每种边权可能的方案数相乘就是答案了(注意判断能否联通,如果跑第一遍最小生成树都建不出来那就不连通输出$0$就好了),接下来请看图。

图中的最小生成树大小显然为3条1组成,但是如果你选择边权为1的边3条且两个端点不在同一联通块内,那么都是可以的

由此我们来引出联通块的概念,如果是最小生成树,那么连任意一条边的之前,两个端点一定在不同的联通块内,而且这个联通块只受到比他权值小或相等的边的影响,不然最小生成树还不如把大的边替换成它。那么这题大致思路就十分明确了,对于每一种边权枚举子集然后连接,并且每次枚举都要把联通块还原回连这种边权之前的状态(这种边权子集任意连接后的联通块状态是一样的,所以对于下一种边权来说之前联通块的状态一定固定),所以开三个fa数组并查集维护记录就好了,相当于是滚动存储。然后直接爆枚出解即可,我的算法和别人的不大一样,不需要撤回(并查集断边),因为我是枚举子集的,所以可以用路径压缩。时间复杂度为$O(2^{该边权条数}*不同边权种类数*n)$,因为不同边权种类数变大的话每种边权条数就会变少,所以大致最坏复杂度大概是$O(100*100*1024)$可以通过此题。

代码

#include<bits/stdc++.h>
#define Mod 31011
#define Maxm 1005
#define Maxn 105
using namespace std;
vector<int> vec[Maxm];
int n,m,anss=1,lsh[Maxm],fa[Maxn],cnt=0,tree_tot[Maxm],graph_tot[Maxm],last_fa[Maxn],tmp_fa[Maxn],num=0,ans=0;
struct edge{int u,v,w;}t[Maxm];
inline void read(int &x){int f=1;x=0;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}x*=f;}
inline int getfa(int x){if (x==fa[x]) return x;return fa[x]=getfa(fa[x]);}
bool cmp(edge a,edge b){return a.w<b.w;}
inline int count_one(int x){int res=0;for (int i=0;i<10;i++) if ((x>>i)&1) res++;return res;}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++) fa[i]=i,tmp_fa[i]=i;
	for (int i=1;i<=m;i++) read(t[i].u),read(t[i].v),read(t[i].w),lsh[i]=t[i].w;
	sort(lsh+1,lsh+m+1);
	int cnt=unique(lsh+1,lsh+m+1)-lsh-1;
	for (int i=1;i<=m;i++) t[i].w=lower_bound(lsh+1,lsh+cnt+1,t[i].w)-lsh;
	sort(t+1,t+m+1,cmp);
	for (int i=1;i<=m;i++) vec[t[i].w].push_back(i),graph_tot[t[i].w]++;
	for (int i=1;i<=m;i++){int fx=getfa(t[i].u),fy=getfa(t[i].v);if (fx==fy) continue;fa[fx]=fy;num++;tree_tot[t[i].w]++;if (num==n-1) break;} 
	if (num!=n-1) return puts("0"),0;
	for (int i=1;i<=cnt;i++)
	{
		for (int j=1;j<=n;j++) last_fa[j]=tmp_fa[j];ans=0;
		for (int E=0;E<=(1<<graph_tot[i])-1;E++)
		{
			int cnnt=count_one(E);
			bool flag=0;
			if (cnnt==tree_tot[i]) 
			{
				for (int j=1;j<=n;j++) fa[j]=last_fa[j];
				for (int j=0;j<graph_tot[i];j++) {if ((E>>j)&1){int fx=getfa(t[vec[i][j]].u),fy=getfa(t[vec[i][j]].v);if (fx==fy) {flag=1;break;} fa[fx]=fy;}}
				if (flag==0) {for (int j=1;j<=n;j++) tmp_fa[j]=fa[j];ans++;ans%=Mod;}
			}	
		}
		anss=(anss*ans)%Mod;
	}
	cout<<anss<<endl;
	return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇