Solution -「JSOI2008」「洛谷 P4208」最小生成树计数

\(\mathcal{Description}\)

link.

给定带权简单无向图，求其最小生成树个数。

顶点数 \(n\le10^2\)，边数 \(m\le10^3\)，相同边权的边数不超过 \(10\)。

\(\mathcal{Solution}\)

先说一个引理：对于一个图的任意两棵最小生成树，其边权集合相等。

简单证明一下，设有两个 最小生成树 的边权集合 \(\{\dots,a,b,\dots\},\{\dots,c,d,\cdots\}\)（省略号处相等，不降排列）。相当于第一棵最小棵树的 \(a,b\) 边替换为了 \(c,d\) 边形成第二棵。不妨设 \(c<a\le b<d\)。那么在第一棵树里先删去 \(a,b\) 边，此时图由三个联通块。加入 \(c\)，显然 \(a,b\) 中的一条是能够再加入的。所以加入 \(d\) 不优，第二棵不是最小生成树，矛盾。

借此，先跑出一棵最小生成树，记为 \(T\)，并得到每种边权的出现次数。枚举每种边权 \(w\)，把 在 \(T\) 中且边权不为 \(w\) 的边加入图，并加入边权为 \(w\) 的所有边。注意加入边权为 \(w\) 的边前需要缩点以保证不会漏选其余边。矩阵树求出此时生成树个数，最后乘法原理乘起来就得到答案了。复杂度 \(\mathcal O(n^3)\)。

\(\mathcal{Code}\)

#include <cstdio>

#include <algorithm>

#define fr first

#define sc second

const int MOD = 31011, MAXN = 100, MAXM = 1000;

int n, m, fa[MAXN + 5], col[MAXN + 5], K[MAXN + 5][MAXN + 5];

bool used[MAXM + 5];

std::pair<int, std::pair<int, int> > eset[MAXM + 5];

inline void init ( const int n ) { for ( int i = 1; i <= n; ++ i ) fa[i] = i; }

inline int find ( const int x ) { return x ^ fa[x] ? fa[x] = find ( fa[x] ) : x; }

inline bool unite ( const int a, const int b ) {

	int u = find ( a ), v = find ( b );

	return u ^ v ? fa[u] = v, true : false;

}

inline void add ( const int u, const int v ) {

	++ K[u][u], ++ K[v][v], -- K[u][v], -- K[v][u];

	if ( K[u][v] < 0 ) K[u][v] += MOD;

	if ( K[v][u] < 0 ) K[v][u] += MOD;

}

inline int det ( const int n ) {

	int ret = 1, swp = 1;

	for ( int i = 1; i < n; ++ i ) {

		for ( int j = i + 1; j < n; ++ j ) {

			for ( ; K[j][i]; std::swap ( K[i], K[j] ), swp *= -1 ) {

				int d = K[i][i] / K[j][i];

				for ( int k = i; k < n; ++ k ) K[i][k] = ( K[i][k] - d * K[j][k] + MOD ) % MOD;

			}

		}

		if ( ! ( ret = ret * K[i][i] % MOD ) ) return 0;

	}

	return ( ret * swp + MOD ) % MOD;

}

int main () {

	scanf ( "%d %d", &n, &m );

	for ( int i = 1, u, v, w; i <= m; ++ i ) {

		scanf ( "%d %d %d", &u, &v, &w );

		eset[i] = { w, { u, v } };

	}

	sort ( eset + 1, eset + m + 1 ), init ( n );

	int cnt = 0;

	for ( int i = 1; i <= m && cnt < n - 1; ++ i ) {

		if ( unite ( eset[i].sc.fr, eset[i].sc.sc ) ) {

			++ cnt, used[i] = true;

		}

	}

	if ( cnt < n - 1 ) return puts ( "0" ), 0;

	int ans = 1;

	for ( int i = 1, j; i <= m; i = j + 1 ) {

		init ( n );

		for ( j = 1; j <= m; ++ j ) {

			if ( used[j] && eset[i].fr ^ eset[j].fr ) {

				unite ( eset[j].sc.fr, eset[j].sc.sc );

			}

		}

		int blk = 0;

		for ( j = 1; j <= n; ++ j ) if ( j == fa[j] ) col[j] = ++ blk;

		for ( j = 1; j <= n; ++ j ) col[j] = col[find ( j )];

		for ( j = 1; j <= blk; ++ j ) for ( int k = 1; k <= blk; ++ k ) K[j][k] = 0;

		for ( j = i; j <= m; ++ j ) {

			add ( col[eset[j].sc.fr], col[eset[j].sc.sc] );

			if ( j == m || eset[j].fr ^ eset[j + 1].fr ) break;

		}

		ans = ans * det ( blk ) % MOD;

	}

	printf ( "%d\n", ans );

	return 0;

}