记录编号	143235	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最小生成树计数	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-12-13 13:27:25	内存使用	0.26 MiB

#include <cctype>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <assert.h>
using namespace std;
template<typename T>inline void getd(T &x){
	char c = getchar(); bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*========================================================*/
const int maxn = 103, maxm = 1003, mod = 31011;
typedef pair<int, pair<int, int> > Edge;
Edge E[maxm];
#define val first
#define u second.first
#define v second.second
int N, M, Ans = 1, *Mat[22], sum;

inline void watch();

struct UFS{
	int pre[maxn];
	void init(int x){for(int i = 0;i <= x;++i)pre[i] = i;}
	int find(int x){return pre[x] == x ? x : pre[x] = find(pre[x]);}
	void link(int a, int b){pre[find(a)] = find(b);}
}ufs, tmpS;
inline void init(){
	getd(N), getd(M);
	int i;
	ufs.init(N);
	for(i = 0;i < M;++i)
		getd(E[i].u), getd(E[i].v), getd(E[i].val);
	for(i = 0;i < 21;++i)
		Mat[i] = new int[22];
	sort(E, E + M);
	sum = N;
}

inline int det(int n){
	int i, j, k, t, ans = 1;
	for(i = 1;i < n;++i){
		for(j = i + 1;j < n;++j){
			while(Mat[j][i]){
				t = Mat[i][i] / Mat[j][i];
				if(t)
					for(k = i;k < n;++k)
						Mat[i][k] = (Mat[i][k] - Mat[j][k] * t) % mod;
				
				swap(Mat[i], Mat[j]), ans = -ans;
			}
		}
		ans = ans * Mat[i][i] % mod;
	}
	return ans;
}
int tmp[22], block[22], cnt;
inline void watch(){
	/*int i, j;
	for(i = 0;i < cnt;++i){
		for(j = 0;j < cnt;++j)
			printf("%5d ", Mat[i][j]);
		printf("\n\n");
	}
	printf("\n\n\n");*/
}
#define index(x) ( lower_bound(block, block + cnt, x) - block )
inline void calc(Edge *A, int len){
	int i, j;
	//int t, adj[22];
	cnt = 1;
	for(i = 0,j = 0;i < len;++i){
		A[i].u = ufs.find(A[i].u);
		A[i].v = ufs.find(A[i].v);
		if(A[i].u == A[i].v)continue;
		tmp[j++] = A[i].u;
		tmp[j++] = A[i].v;
	}
	sort(tmp, tmp + j);
	block[0] = tmp[0];
	for(i = 1;i < j;++i)
		if(tmp[i] != block[cnt-1])block[cnt++] = tmp[i];
	
	for(i = 0;i < cnt;++i)for(j = 0;j < cnt;++j)
		Mat[i][j] = 0;
	
	tmpS.init(cnt);
	
	for(i = 0;i < len;++i){
		if(A[i].u == A[i].v)continue;
		if(ufs.find(A[i].u) != ufs.find(A[i].v))--sum;
		ufs.link(A[i].u, A[i].v);
		A[i].u = index(A[i].u);
		A[i].v = index(A[i].v);
		++Mat[A[i].u][A[i].u];
		++Mat[A[i].v][A[i].v];
		//adj[A[i].u] |= (1 << A[i].v);
		//adj[A[i].v] |= (1 << A[i].u);
		--Mat[A[i].u][A[i].v];
		--Mat[A[i].v][A[i].u];
		tmpS.link(A[i].u, A[i].v);
	}
	int a, b;
	for(i = 1;i < cnt;++i)
		if((a = tmpS.find(i)) != (b = tmpS.find(i-1))){
			++Mat[a][a], ++Mat[b][b];
			//adj[a] |= (1 << b);
			//adj[b] |= (1 << a);
			--Mat[a][b], --Mat[b][a];
			tmpS.link(a, b);
		}
	
	Ans = Ans * det(cnt) % mod;
}
inline void work(){
	int i = 0, j = 1, t;
	while(i < M){
		while(j < M && E[i].val == E[j].val)++j;
		if((t = j - i) > 1)calc(E + i, j - i);
		else if(ufs.find(E[i].u) != ufs.find(E[i].v))
			ufs.link(E[i].u, E[i].v), --sum;
		i = j++;
	}
	if(sum > 1)printf("0\n");
	else 
		printf("%d\n", Ans);
}
int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("bzoj_1016.in", "r", stdin);
	freopen("bzoj_1016.out", "w", stdout);
	#endif
	init();
	work();
	
	return 0;
}