[BZOJ 1016] [JSOI2008] 最小生成树计数【DFS】

浏览数：50 / 时间：2015年06月09日

题目链接：BZOJ - 1016

题目分析

最小生成树的两个性质：

同一个图的最小生成树，满足：

1）同一种权值的边的个数相等

2）用Kruscal按照从小到大，处理完某一种权值的所有边后，图的连通性相等

这样，先做一次Kruscal求出每种权值的边的条数，再按照权值从小到大，对每种边进行 DFS，求出这种权值的边有几种选法。

最后根据乘法原理将各种边的选法数乘起来就可以了。

特别注意：在DFS中为了在向下DFS之后消除决策影响，恢复f[]数组之前的状态，在DFS中调用的Find()函数不能路径压缩。

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MaxN = 100 + 5, MaxM = 1000 + 5, Mod = 31011;

int n, m, Top, Sum, Cnt;
int f[MaxN], L[MaxM], R[MaxM], Num[MaxM];

typedef long long LL;
LL Ans;

struct Edge
{
	int u, v, w; 
} E[MaxM];

inline bool Cmp(Edge e1, Edge e2) 
{
	return e1.w < e2.w;
}

inline int Find(int x, int o) 
{
	int i, j, k;
	j = x; 
	while (j != f[j]) j = f[j];
	if (o == 1) return j;
	i = x;
	while (i != j) 
	{
		k = i;
		i = f[i];
		f[k] = j;
	}
	return j;
}

void DFS(int Type, int x, int y) 
{
	if (x == R[Type] + 1) 
	{
		if (y == Num[Type]) ++Cnt;
		return;
	}
	int fx, fy;
	fx = Find(E[x].u, 1); fy = Find(E[x].v, 1);
	if (fx != fy)
	{
		f[fx] = fy;
		DFS(Type, x + 1, y + 1);
		f[fx] = fx;
	}
	DFS(Type, x + 1, y);
}

int main() 
{
	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);
	sort(E + 1, E + m + 1, Cmp);
	Top = 0; Sum = 0;
	int fx, fy;
	for (int i = 1; i <= n; ++i) f[i] = i;
	for (int i = 1; i <= m; ++i) 
	{
		if (i == 1 || E[i].w != E[i - 1].w) L[++Top] = i;
		R[Top] = i;
		fx = Find(E[i].u, 0); fy = Find(E[i].v, 0);
		if (fx != fy) 
		{
			f[fx] = fy;
			++Num[Top];
			++Sum;
		}
	}
	if (Sum != n - 1) 
	{
		printf("0\n");
		return 0;
	}
	for (int i = 1; i <= n; ++i) f[i] = i;
	Ans = 1;
	for (int i = 1; i <= Top; ++i) 
	{
		if (Num[i] == 0) continue;
		Cnt = 0;
		DFS(i, L[i], 0);
		Ans = Ans * (LL)Cnt % Mod;
		for (int j = L[i]; j <= R[i]; ++j) 
		{
			fx = Find(E[j].u, 0); fy = Find(E[j].v, 0);
			if (fx != fy) f[fx] = fy;
		}
	}
	printf("%d\n", (int)Ans);
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

[BZOJ 1016] [JSOI2008] 最小生成树计数【DFS】