【BZOJ1016】最小生成树计数

  标算应该是DFS+kruskal，其中DFS是计算选一些权值相等的边的方案数的。但是感觉写DFS不高贵就敲Matrix-Tree了，尽管代码量上升了很多。

  Build_Graph1将当前连通块缩点，使用一些权值相等的有用的边，将连通块连接起来，对应的值放进行列式里。

  Build_Graph2将Build_Graph1中剩下的彼此之间没有联通的连通块连接起来（原图中并没有这些边），由于这些边在计算时是必选的，所以不影响答案。

  当然直接写DFS就好了没必要像Zarxdy34一样这么SB...

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int maxn=110,maxm=1010,mo=31011;

struct Edge {int x,y,c;}E[maxm];
bool cmp(const Edge &a,const Edge &b) {return a.c<b.c;}

struct Matrix
{
	int a[maxn][maxn];
	int n;

	void Init() {memset(a,0,sizeof(a));}
	int* operator[] (int x) {return a[x];}

	int det()
	{
		int ans=1;
		for (int i=1;i<n;i++) for (int j=1;j<n;j++) a[i][j]=(a[i][j]%mo+mo)%mo;
		for (int i=1;i<n;i++)
		{
			for (int j=i+1;j<n;j++) while (a[j][i])
			{
				int x=a[i][i]/a[j][i];
				for (int k=i;k<n;k++) a[i][k]=(a[i][k]-x*a[j][k]%mo+mo)%mo;
				for (int k=i;k<n;k++) swap(a[i][k],a[j][k]);
				ans=-ans;
			}
		}
		if (ans==-1) ans+=mo;
		for (int i=1;i<n;i++) ans=ans*a[i][i]%mo;
		return ans;
	}
}M;

int Find(int *f,int x) {return x==f[x]?x:f[x]=Find(f,f[x]);}

int f[maxn],f2[maxn];
int vis[maxn];
int id[maxn],ids;
int n,m,ans;

void Build_Graph1(int l,int r)
{
	memset(vis,0,sizeof(vis));
	memset(id,0,sizeof(id));
	ids=0;
	for (int i=l;i<=r;i++) if (Find(f,E[i].x)!=Find(f,E[i].y)) f2[Find(f2,E[i].x)]=Find(f2,E[i].y),vis[f[E[i].x]]=1,vis[f[E[i].y]]=1;
	for (int i=1;i<=n;i++) if (vis[i]) id[i]=++ids;
	for (int i=l;i<=r;i++) if (f[E[i].x]!=f[E[i].y])
	{
		int idx=id[f[E[i].x]],idy=id[f[E[i].y]];
		M[idx][idx]++;M[idy][idy]++;
		M[idx][idy]--;M[idy][idx]--;
	}
	M.n=ids;
}

int q[maxn],qn;

void Build_Graph2(int l,int r)
{
	memset(vis,0,sizeof(vis));
	for (int i=l;i<=r;i++) if (f[E[i].x]!=f[E[i].y]) vis[Find(f2,E[i].x)]=1,vis[Find(f2,E[i].y)]=1;
	qn=0;
	for (int i=1;i<=n;i++) if (vis[i]) q[++qn]=i;
	for (int i=1;i<qn;i++)
	{
		int idx=id[q[i]],idy=id[q[i+1]];
		M[idx][idx]++;M[idy][idy]++;
		M[idx][idy]--;M[idy][idx]--;
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].c);
	for (int i=1;i<=n;i++) f[i]=f2[i]=i;
	sort(E+1,E+1+m,cmp);
	ans=1;
	for (int l=1,r=1;l<=m;l=r+1)
	{
		r=l;
		while (r<m && E[r+1].c==E[l].c) r++;
		M.Init();
		Build_Graph1(l,r);
		Build_Graph2(l,r);
		ans=ans*M.det()%mo;
		for (int i=1;i<=n;i++) f[i]=Find(f2,i);
	}
	for (int i=1;i<n;i++) if (Find(f,i)!=Find(f,i+1)) {printf("0\n");return 0;}
	printf("%d\n",ans);
	return 0;
}