最小生成树计数

最小生成树计数

rt.1<=n<=100; 1<=m<=1000

先求一遍最小生成树以后， 把我们考虑同一边权的所有边。

我们发现，所有最小生成树中，同一边权的那些边，其实连了固定的一堆点。这是一个最小生成树的性质。

因此，只需对于同一边权的边，统计连这些点有几种连法。用乘法原理乘所有边就得到了答案。

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=1e5+5, maxm=1e5+5, mod=1e9+7;
struct Edge{
	int x, y, v;
}e[maxm];
int cnte;
bool cmp(const Edge &a, const Edge &b){
	return a.v<b.v; }
	
int fa[maxn];
int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
map<int, int> maap;
int n, m, ans=1;

int popcount(int x){ int re=0;
	while (x) re+=x&1, x>>=1; return re; }

int main(){
	scanf("%d%d", &n, &m); int x, y, v, t=0;
	for (int i=0; i<m; ++i){
		scanf("%d%d%d", &x, &y, &v);
		e[cnte++]=(Edge){x, y, v}; }
	sort(e, e+m, cmp);
	for (int i=0; i<m; ++i){
		if (find(e[i].x)!=find(e[i].y)){
			++maap[e[i].v]; fa[find(e[i].x)]=find(e[i].y);
			if (++t==n-1) break;
		}
	}
	if (t<n-1){ puts("0"); return 0; }
	memset(fa, 0, sizeof(fa)); int j=0, flag, now;
	for (int i=1; i<=m; ){
		for (j=i; e[j].v==e[j+1].v; ++j);
		if (!maap[e[i].v]) continue;  //这个边权里必须有能选的点
		for (int S=0; S<(1<<j-i+1); ++S){
			if (popcount(S)!=maap[e[i].v]) continue;
			flag=1; now=0;
			for (int k=i; k<=j; ++k){
				if (S>>(k-i)&1){
					if (find(e[i].x)==find(e[i].y)){
						flag=0; break; }
				}
			}
			if (flag) ++now;
		}
		(ans*=now)%=mod;
		i=j+1;
	}
	printf("%d
", ans);
	return 0;
}

注：代码勿看（qwq）