记录编号	366058	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最小生成树计数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2017-01-22 15:28:41	内存使用	3.79 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10,p=31011;
struct edge{int f,t,l;}w[N];
bool cmp(const edge &x,const edge &y){return x.l<y.l;}
int n,m,fa[N],pos[N],Fa[N],sum,ans=1;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);}
struct matrix{
	int n,a[110][110];
	int abs(){
		int ans=1;
		for (int i=1;i<n;i++){
			for (int j=i+1;j<n;j++)
			while (a[j][i]){//更相损减术 
				int t=a[i][i]/a[j][i];
				for (int k=i;k<n;k++)
					a[i][k]=a[i][k]-a[j][k]*t;
				for (int k=i;k<n;k++)
					swap(a[i][k],a[j][k]);
				ans=-ans;
			}
			ans=ans*a[i][i]%p;
		}
		return (ans+p)%p;
	}
}x;
vector<edge> E[N];
void calc(int Set){
	int cnt=0;
	for (int i=1;i<=n;i++) pos[i]=0;
	for (int i=1;i<=x.n;i++)
		for (int j=1;j<=x.n;j++)
			x.a[i][j]=0;
	for (int i=E[Set].size()-1;i>=0;i--){
		int a=find(E[Set][i].f),b=find(E[Set][i].t);
		if (!pos[a]) pos[a]=++cnt;a=pos[a];
		if (!pos[b]) pos[b]=++cnt;b=pos[b];
		x.a[a][a]++;x.a[b][b]++;
		x.a[a][b]--;x.a[b][a]--;
	}
	x.n=cnt;
	ans=ans*x.abs()%p;
	E[Set].clear();
}
int main()
{
	freopen("bzoj_1016.in","r",stdin);
	freopen("bzoj_1016.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) Fa[i]=fa[i]=i;
	for (int i=1;i<=m;i++)
		scanf("%d%d%d",&w[i].f,&w[i].t,&w[i].l);
	sort(w+1,w+m+1,cmp);
	for (int i=1;i<=m;){
		int last=i,flag=w[i].l,cnt=0;
		for (int i=1;i<=n;i++) pos[i]=0;
		for (;i<=m&&w[i].l==flag;i++){
			int a=Find(w[i].f),b=Find(w[i].t);
			if (a==b) continue;
			Fa[Find(a)]=Find(b);
			sum++;
		}
		for (int p=last;p<i;p++)
			E[Find(w[p].f)].push_back(w[p]);
		for (int p=1;p<=n;p++) calc(p);
		for (int p=last;p<i;p++)
			fa[find(w[p].f)]=find(w[p].t);
	}
	if (sum<n-1) ans=0;
	printf("%d\n",ans);
	return 0;
}