JSOI2008 最小生成树计数

未分类

首先考虑 Kruskal 算法的过程，实际上是将边权升序排序后全部加入最小生成树再去掉所有的环，所以对于每种不同的最小生成树每种边权的数量都是一定的，同时也可以发现在加入一种新的边权后联通块的情况都是一模一样的，因为同种边权数量不超过 $10$，所以直接爆搜每种边权选哪几个，再乘起来，中途使用不路径压缩的并查集（为了方便 DFS 的撤销

#include <iostream>
#include <cstdio>
#include <algorithm>
const int MAXN = 100;
const int MAXM = 10000;
const int MOD = 31011;
int n, m, cnt, res;
int L[MAXM | 1], R[MAXM | 1], sum[MAXM | 1], fset[MAXN | 1];
struct Edge {
  int from, to, w;
  Edge() : from(0), to(0), w(0) {}
  friend bool operator< (const Edge &lhs, const Edge &rhs) {
    return lhs.w < rhs.w;
  }
} e[MAXM | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
int f(int x) {
  return fset[x] == x ? x : f(fset[x]);
}
void dfs(int x, int id, int tot) {
  if (x == R[id] + 1) {
    if (tot == sum[id]) ++res;
    return;
  }
  int from = f(e[x].from), to = f(e[x].to);
  if (from != to) {
    fset[from] = to;
    dfs(x + 1, id, tot + 1);
    fset[from] = from;
  }
  dfs(x + 1, id, tot);
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; ++i) {
    e[i].from = read();
    e[i].to = read();
    e[i].w = read();
  }
  std::sort(e + 1, e + 1 + m);
  for (int i = 1; i <= n; ++i) fset[i] = i;
  int ans = 0;
  for (int i = 1, j = 0; i <= m; ++i) {
    if (e[i].w != e[i - 1].w) {
      R[cnt] = i - 1;
      L[++cnt] = i;
    } 
    int x = f(e[i].from), y = f(e[i].to);
    if (x != y) {
      fset[x] = y;
      ++sum[cnt];
      ++j;
    }
    if (i == m && j != n - 1) {
      puts("0");
      return 0;
    }
  }
  R[cnt] = m;
  ans = 1;
  for (int i = 1; i <= n; ++i) fset[i] = i;
  for (int i = 1; i <= cnt; ++i) {
    res = 0;
    dfs(L[i], i, 0);
    ans = ans * res % MOD;
    for (int j = L[i]; j <= R[i]; ++j) {
      int x = f(e[j].from), y = f(e[j].to);
      if (x != y) fset[x] = y;
    }
  }
  printf("%d\n", ans);
  return 0;
}