记录编号	418157	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最小生成树计数	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2017-06-29 13:17:48	内存使用	0.30 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MOD = 31011;
const int MAXN = 110;
const int MAXM = 1010;
struct edge {
	int u, v, d;
	inline bool operator<(edge rhs) const {
		return d < rhs.d;
	}
} E[MAXM];
 
int Ans = 1, N, M;

struct FUS {
	int set[MAXN];
	int find(int u) {
		return (set[u] == u) ? u : (set[u] = find(set[u]));
	}
	bool join(int u, int v) {
		int pu = find(u), pv = find(v);
		if(pu != pv) set[pu] = pv;
		return pu != pv;
	}
	void init() {
		for(int i = 1; i <= N; i++) set[i] = i;
	}
	int count() {
		int ans = 0;
		for(int i = 1; i <= N; i++) if(set[i] == i) ans++;
		return ans;
	}
} setL, setN, setR;
 
int main() {
	freopen("bzoj_1016.in", "rt", stdin);
	freopen("bzoj_1016.out", "wt", stdout);

	int i, k, u, v;
	scanf("%d%d", &N, &M);
	for(i=0;i<M;i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].d);
	sort(E, E + M);
 
	//bf
	setL.init(); setR.init();
 
	int begin = 0, set, len, s, cnt;
	for(k=0;k<M;k++) if(k == M - 1 || (E[k].d != E[k+1].d)) {
		//calc right value
		for(i=begin;i<=k;i++) setR.join(E[i].u, E[i].v);
 
		//bf cur state
		len = k - begin + 1; cnt = 0;
		for(set=0;set<(1 << len);set++) {
			bool ok = 1;
			for(i=1;i<=N;i++) setN.set[i] = setL.set[i];
			for(s=0;s<len;s++) if((set >> s) & 1) {
				u = E[begin + s].u; v = E[begin + s].v;
				if(!setN.join(u, v)) {
					ok = 0; break;
				}
			}
			if(ok) {
				if(setN.count() != setR.count()) ok = 0;
			}
			cnt += ok;
		}
		
		Ans = (Ans * cnt) % MOD;
		//update MST
		//Run Kruskal
		for(i=1;i<=N;i++) setL.set[i] = setR.set[i];
		begin = k + 1;
	}
	//Check
	k = 0;
	for(i=1;i<=N;i++) {
		u = setR.find(i);
 
		if(k && k != u) Ans = 0;
		else k = u;
	}
	printf("%d", Ans);
}