【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1016
【题意】
【题解】
/*
接上一篇文章;
这里用matrix-tree定理搞最小生成树个数;
对于每一种相同边权的边;
当做一个阶段;
这个阶段,我们需要看看这个边权的边能连接哪些联通块;
这里的联通块可以缩为一个点;
这样就相当于在一些点中间插入边;
然后问你这些边能够生成的生成树的个数;
即每个阶段都做一遍matrix-tree定理;
martrix-treee定理想要做的话;
你得先得出一张图,最好弄出它的邻接矩阵;
然后可以这样吧。
把这张图缩点之后的节点都标成新的节点;
然后根据新添加进来的边;
建立一张新的图,
然后在这张新图上求生成树;
根据前一篇的分析可知这样的生成树一定是最小生成树的一部分;
建立新图的话也不会难吧;
如果节点之前没出现过就递增节点就好;
然后统计这张新图里面节点的个数;
然后处理出邻接矩阵和度数就能搞了;
不过这样处理会有重边的哦;
当然这个定理也能处理有重边的情况,所以不慌.
每次把生成树的个数根据乘法原则乘到答案上就好
(新的图上可能会有多个连通块,要每个连通块分别算,不然整张图都不是联通的,你再用
整张图去求的话会出错)
(初始化什么的一定要认真检查啊);
(这个行列式的求法不要用double类,不然精度不够,用int。。不知道为什么可以用int..)
*/
推荐一个题解吧
http://www.cnblogs.com/flipped/p/5769228.html
要记住是度数矩阵减去邻接矩阵啊.
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 110;
const int M = 1e3 + 100;
const int MOD = 31011;
struct abc
{
int x, y, z;
};
int n, m,tot,cnt = 0;
int f[N],D[N][N],A[N][N],C[N][N],ka[N],g[N][N];
int bo[N];
abc bian[M];
double a[N][N];
vector <int> v[N];
long long ans = 1;
bool cmp1(abc a, abc b)
{
return a.z < b.z;
}
int ff(int x)
{
if (f[x] == x) return x;
else
return f[x] = ff(f[x]);
}
int fk(int x)
{
if (ka[x] == x) return x;
else
return ka[x] = fk(ka[x]);
}
int cl(int c[N][N], int n) {
int i, j, k, t, ret = 1;
for (i = 1; i<=n-1; i++) {
for (j = i + 1; j<=n-1; j++)
while (c[j][i]) {
t = c[i][i] / c[j][i];
for (k = i; k<n; k++)
c[i][k] = (c[i][k] - c[j][k] * t) % MOD;
swap(c[i], c[j]);
ret = -ret;
}
if (c[i][i] == 0)
return 0;
ret = ret*c[i][i] % MOD;
}
return (ret + MOD) % MOD;
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
rei(n), rei(m);
rep1(i, 1, m)
rei(bian[i].x), rei(bian[i].y), rei(bian[i].z);
sort(bian + 1, bian + 1 + m,cmp1);
ans = 1;
rep1(i, 1, n)
f[i] = i,ka[i] = i;
rep1(i, 1, m)
{
int l = i, r = i;
while (r + 1 <= m && bian[r + 1].z == bian[l].z) r++;
rep1(j, 1, n)
rep1(jj, 1, n)
g[j][jj] = 0;
rep1(j, 1, n)
bo[j] = 0;
rep1(j, l, r)
{
int x = bian[j].x, y = bian[j].y;
int r1 = ff(x), r2 = ff(y);
if (r1 != r2)
{
int rr1 = fk(r1), rr2 = fk(r2);
if (rr1 != rr2)
ka[rr1] = rr2;
bo[r1] = true, bo[r2] = true;
g[r1][r2]++, g[r2][r1]++;
}
}
rep1(j, 1, n)
v[j].clear();
rep1(j, 1, n)
if (bo[j])
v[fk(j)].push_back(j);
rep1(j,1,n)
if (int(v[j].size()) > 1)
{
rep1(k, 1, n)
rep1(kk, 1, n)
D[k][kk] = A[k][kk] = 0;
int len = v[j].size();
rep1(k,0,len-2)
rep1(l, k + 1, len - 1)
{
int x = v[j][k], y = v[j][l];
if (g[x][y])
{
D[k+1][k+1] += g[x][y], D[l+1][l+1] += g[x][y];
A[l+1][k+1] = A[k+1][l+1] = g[x][y];
}
}
rep1(k, 1,len )
rep1(kk, 1, len)
C[k][kk] = D[k][kk] - A[k][kk];
tot = len;
ans = (ans*cl(C,len)) % MOD;
}
rep1(j, l, r)
{
int x = bian[j].x, y = bian[j].y;
int r1 = ff(x), r2 = ff(y);
if (r1 != r2)
{
f[r1] = r2;
cnt++;
}
}
rep1(j, 1, n)
ka[j] = f[j];
i = r;
}
if (cnt != n - 1)
return puts("0"),0;
printf("%lld
", ans);
return 0;
}