C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 384K, 提交时间: 2019-12-27 10:52:41

#include<bits/stdc++.h>
using namespace std;


vector<int> p;

int find(int x) {
  return p[x] == x? x : (p[x] = find(p[x]));
}

struct Edge {
  int u, v, w;
};

int main() {
  int n, m; cin >> n >> m;
  p.resize(n + 1); for (int i = 1; i <= n; i++)  p[i] = i;
  vector<Edge> edges(m); for (auto &e: edges) cin >> e.u >> e.v >> e.w;
  sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
    return a.w < b.w;
  });
  map<int, int> M;

  int eCnt = 0;
  for (auto &e: edges) {
    int x = e.u, y = e.v;
    int px = find(x), py = find(y);
    if (px != py) p[px] = py, M[e.w]++, eCnt++;
  }
  if (eCnt < n - 1) {
    cout << 0 << endl;
    return 0;
  } 
  for (int i = 1; i <= n; i++) p[i] = i;
  int tot = 1;
  for (int l = 0, r = 0; l < m; l = r) {
    while (r < m && edges[r].w == edges[l].w) r++;
    auto tmp = p;
    int N = r - l;
    Edge* E = edges.data() + l;
    for (int i = 0; i < N; i++) {
      int x = E[i].u, y = E[i].v;
      int px = find(x), py = find(y);
      if (px > py) swap(px, py);
      if (px != py) p[py] = px;
    }
    for (int i = 1; i <= n; i++) p[i] = find(i);
    auto tmp2 = p;
    int cnt = 0;
    for (int mask = 0; mask < (1<<N); mask++) if (__builtin_popcount(mask) == M[edges[l].w]) {
      p = tmp;
      for (int i = 0; i < N; i++) if (mask & (1<<i)) {
        int x = E[i].u, y = E[i].v;
        int px = find(x), py = find(y);
        if (px > py) swap(px, py);
        if (px != py) p[py] = px;
      }
      for (int i = 1; i <= n; i++) p[i] = find(i);
      if (tmp2 == p) cnt++;
    }
    p = tmp2;
    tot = tot * cnt % 31011;
  }
  cout << tot << endl;

}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2020-07-29 17:36:46

#include <cstdio>
#include <algorithm>

const int N=105,M=1e3+5;
const int mod=31011;
int n,m,cnt,sum,l[M],r[M],c[M],fa[N];
struct Edge {
	int u,v,w;
	bool operator < (const Edge &b) const {
		return w<b.w;
	}
}e[M];

int find(int x) {
	return fa[x]==x?x:find(fa[x]);
}
void dfs(int now,int x,int num) {
	if(now>r[x]) {
		sum+=(num==c[x]);
		return;
	}
	int fu=find(e[now].u),fv=find(e[now].v);
	if(fu!=fv) {
		fa[fu]=fv;
		dfs(now+1,x,num+1);
		fa[fu]=fu,fa[fv]=fv;
	}
	dfs(now+1,x,num);
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	std::sort(e+1,e+m+1);
	for(int i=1;i<=n;++i) fa[i]=i;
	int tot=0;
	for(int i=1;i<=m;++i) {
		if(e[i].w!=e[i-1].w) r[cnt]=i-1,l[++cnt]=i;
		int fu=find(e[i].u),fv=find(e[i].v);
		if(fu!=fv) ++c[cnt],fa[fu]=fv,++tot;
	}
	r[cnt]=m;
	if(tot!=n-1) return puts("0"),0;
	for(int i=1;i<=n;++i) fa[i]=i;
	int ans=1;
	for(int i=1;i<=cnt;++i) {
		sum=0,dfs(l[i],i,0),ans=ans*sum%mod;
		for(int j=l[i];j<=r[i];++j) fa[find(e[j].u)]=find(e[j].v);
	}
	printf("%d\n",ans);
	return 0;
}