记录编号	146357	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最小生成树计数	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	2.579 s
提交时间	2015-01-14 21:28:45	内存使用	7.06 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x3fffffff;
//==============struct declaration==============
struct adj{
  int from,to,len;
  adj(int from=0,int to=0,int len=0):from(from),to(to),len(len){}
  bool operator <(const adj &rhs) const{
    return len<rhs.len;
  }
};
//==============var declaration=================
const int MAXN=1010;
const int MOD=31011;
int n,m;
int hash[MAXN],root[MAXN],prevroot[MAXN],M[MAXN][MAXN];
int *prev,*next;
bool vis[MAXN];
adj Edge[MAXN];
//==============function declaration============
int quickpow(int a,int Exp);
int inv(int x){return quickpow(x,MOD-2);}
int findr(int x,int *R){return R[x]==x?x:R[x]=findr(R[x],R);}
int Solve_Matrix(int N);
//==============main code=======================
int main()
{  
#define FILE__
#ifdef FILE__
  freopen("bzoj_1016.in","r",stdin);
  freopen("bzoj_1016.out","w",stdout);
#endif  
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
    scanf("%d%d%d",&Edge[i].from,&Edge[i].to,&Edge[i].len);
  sort(Edge+1,Edge+1+m);
  for(int i=1;i<=n;i++) root[i]=prevroot[i]=i;
  prev=prevroot,next=root;
  long long ans=1;
  for(int x=1;x<=m;x++){
    vector <adj> G;
    for(int i=x;i<=m&&Edge[i].len==Edge[x].len;i++){
      int s=findr(Edge[i].from,prev),e=findr(Edge[i].to,prev);
      if (s==e) continue;
      G.push_back(Edge[i]);
    }
    for(int i=x;i<=m&&Edge[i].len==Edge[x].len;i++){
       x=i;
      if (findr(Edge[i].from,next)==findr(Edge[i].to,next)) continue;
      next[findr(Edge[i].from,next)]=findr(Edge[i].to,next);
    }
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++){
      if (vis[i]) continue;
      memset(hash,-1,sizeof(hash));memset(M,0,sizeof(M));
      int cnt=0;
      for(int j=0;j<G.size();j++){
        if (findr(G[j].from,next)==findr(i,next)){
          int s=findr(G[j].from,prev),e=findr(G[j].to,prev);
          if (hash[s]==-1) hash[s]=++cnt;
          if (hash[e]==-1) hash[e]=++cnt;
          M[hash[s]][hash[e]]--;M[hash[e]][hash[s]]--;
          M[hash[s]][hash[s]]++;M[hash[e]][hash[e]]++;
        }
      }
      for(int j=1;j<=n;j++)
        if (findr(i,next)==findr(j,next)) vis[j]=true;
      int temp=Solve_Matrix(cnt);
      ans=(ans*temp)%MOD;
    }  
    for(int i=1;i<=n;i++)
      prev[i]=next[i];
  }
  for(int i=1;i<=n;i++)
    if (findr(1,next)!=findr(i,next)){
      printf("0\n");
      return 0;
    }
  printf("%lld\n",ans);
  return 0;
}
//================fuction code====================
int quickpow(int a,int Exp){
  if (Exp==0) return 1;
  if (Exp==1) return 0;
  int temp=quickpow(a,Exp/2);
  temp=(temp*temp)%MOD;
  if (Exp&1) temp=(temp*a)%MOD;
  return temp;
}
int Solve_Matrix(int N){
  long long ret=1;N--;
  for(int x=1;x<=N;x++){//处理第x行 
    for(int r=x+1;r<=N;r++)
      while (M[r][x]){//类似辗转相除法将其化为0 
        int t=M[x][x]/M[r][x];
        for(int i=x;i<=N;i++)
          M[x][i]=(M[x][i]-M[r][i]*t)%MOD;
        for(int i=x;i<=N;i++)
          swap(M[x][i],M[r][i]);
        ret=-ret;//交换矩阵两行，行列式取反 
      }
    ret=(ret*M[x][x])%MOD;
  }
  return (ret+MOD)%MOD;
}