题意
某图有n(1<=n<=100)个点，m(0<=m<=1000)条边，求该图的“最小生成树的个数%p”(1<=p<=1000000000)。
题解
需要结合Matrix-Tree定理和Kruskal算法。
首先将所有的边按照边长从小到大排序，相同长度的边分为一组。从长度小的组开始处理。
对于每组边，用一个并查集（disSet）表示加入这组边之前的连通性，另一个并查集（tempSet）表示加入这组边之后的连通性。
将disSet中每个连通分量视为一个点，得到一个新的图G。
再将图G根据tempSet分为不同的连通分量，将其每个连通分量视为一个图，由Matrix-Tree定理计算通过该组边可以得到的生成树的个数。然后将所有得到的个数累乘即可。
注意计算过程中对p取模，另外此题将只有一个点的图的生成树个数视为0。
代码
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int E = 2;
const int INF = 0x3f3f3f3f;
const int MAX_EDGE = 1000;
const int MAX_VERTEX = 110;
//并查集类
class DisjointSet {
public:
vector<int> height, sets;
DisjointSet() {}
DisjointSet(int n) {
height.resize(n, 0);
sets.resize(n, 0);
for(int i=0; i<n; ++i) {
sets[i] = i;
height[i] = 0;
}
}
DisjointSet(const DisjointSet &tempSet) {
int n = tempSet.height.size();
height.resize(n, 0);
sets.resize(n, 0);
for(int i=0; i<n; ++i) {
sets[i] = tempSet.sets[i];
height[i] = tempSet.height[i];
}
}
int getSet(int x) {
if(x != sets[x]) sets[x] = getSet(sets[x]);
return sets[x];
}
void unite(int x, int y) {
x = getSet(x), y = getSet(y);
if(x == y) return;
if(height[x] > height[y]) sets[y] = x;
else {
sets[x] = y;
if(height[x] == height[y]) ++height[y];
}
}
bool same(int x, int y) {return getSet(x) == getSet(y);}
};
//边类
class Edge {
public:
int depa, dest, dist;
Edge(int depa=0, int dest=0, int dist=0): depa(depa), dest(dest), dist(dist) {}
bool operator < (const Edge &tempEdge) const {
return dist < tempEdge.dist;
}
};
//矩阵类，用于计算行列式
class Matrix {
public:
int row, column;
long long **num;
Matrix(int row, int column): row(row), column(column) {
num = new long long *[row];
for(int i=0; i<row; ++i) {
num[i] = new long long [column];
for(int j=0; j<column; ++j)
num[i][j] = 0;
}
}
Matrix(int row, int column, long long **tempNum): row(row), column(column) {
num = new long long *[row];
for(int i=0; i<row; ++i) {
num[i] = new long long [column];
for(int j=0; j<column; ++j)
num[i][j] = tempNum[i][j];
}
}
Matrix(const Matrix &tempMatrix): row(tempMatrix.row), column(tempMatrix.column) {
num = new long long *[row];
for(int i=0; i<row; ++i) {
num[i] = new long long [column];
for(int j=0; j<column; ++j)
num[i][j] = tempMatrix.num[i][j];
}
}
long long determinant(int row, long long mod) {
long long **tempNum = new long long *[row];
for(int i=0; i<row; ++i) {
tempNum[i] = new long long [row];
for(int j=0; j<row; ++j)
tempNum[i][j] = num[i][j]%mod;
}
long long res = 1;
bool flag = false;
for(int i=0; i<row; ++i) {
for(int j=i+1; j<row; ++j) {
int x = i, y = j;
while(tempNum[y][i]) {
long long temp0 = tempNum[x][i]/tempNum[y][i];
for(int k=i; k<row; ++k)
tempNum[x][k] = (tempNum[x][k] - tempNum[y][k]*temp0)%mod;
swap(x, y);
}
if(x != i) {
for(int k=0; k<row; ++k)
swap(tempNum[x][k], tempNum[y][k]);
flag ^= true;
}
}
if(tempNum[i][i] == 0) return 0;
else res = (res*tempNum[i][i])%mod;
}
if(flag) res = -res;
if(res < 0) res += mod;
return res%mod;
}
void display(int row, int column) {
for(int i=0; i<row; ++i)
for(int j=0; j<column; ++j)
cout << num[i][j] << (j==column-1 ? '\n':' ');
}
void display() {display(row, column);}
};
vector<Edge> edge;
bool vis[MAX_VERTEX + E];
//计算最小生成树个数的函数
long long countMST(int nVertex, long long mod) {
if(edge.size() == 0) return 0;
sort(edge.begin(), edge.end());
DisjointSet disSet(nVertex);//用于记录每组边加入之前的连通性
memset(vis, false, sizeof(vis));
long long res = 1;
for(int i=0; i<edge.size();) {
Matrix kirchhoff(nVertex, nVertex);
DisjointSet tempSet = disSet;//用于记录每组边加入之后的连通性
int nowEdge = i;
for(; nowEdge<edge.size(); ++nowEdge) {
if(edge[i].dist != edge[nowEdge].dist) break;//当边的长度不同时退出，即一组一组地处理
int x = edge[nowEdge].depa, y = edge[nowEdge].dest;
tempSet.unite(x, y);
x = disSet.getSet(x), y = disSet.getSet(y);
++kirchhoff.num[x][x], ++kirchhoff.num[y][y];
--kirchhoff.num[x][y], --kirchhoff.num[y][x];
vis[x] = vis[y] = true;
}
vector<int> component[MAX_VERTEX + E];//记录加入每组边之后不同连通分量有哪些点
for(int j=0; j<nVertex; ++j)
if(vis[j]) {
component[tempSet.getSet(j)].push_back(j);
vis[j] = false;
}
for(int j=0; j<nVertex; ++j)
if(component[j].size() > 1) {
int len = component[j].size();
Matrix tempMatrix(len, len);
for(int x=0; x<len; ++x)
for(int y=x+1; y<len; ++y) {
int tempX = component[j][x], tempY = component[j][y];
tempMatrix.num[x][x] = kirchhoff.num[tempX][tempX];
tempMatrix.num[y][y] = kirchhoff.num[tempY][tempY];
tempMatrix.num[x][y] = kirchhoff.num[tempX][tempY];
tempMatrix.num[y][x] = kirchhoff.num[tempY][tempX];
}
res = (res*tempMatrix.determinant(len-1, mod))%mod;
}
i = nowEdge;
disSet = tempSet;
}
for(int i=1; i<nVertex; ++i)
if(!disSet.same(i, i-1))
return 0;
return res%mod;
}
int main() {
int nVertex, nEdge;
long long mod;
while(scanf("%d%d%lld", &nVertex, &nEdge, &mod)!=EOF && nVertex+nEdge+mod!=0) {
edge.clear();
for(int i=0; i<nEdge; ++i) {
int depa, dest, dist;
scanf("%d%d%d", &depa, &dest, &dist);
--depa, --dest;
edge.push_back(Edge(depa, dest, dist));
}
printf("%lld\n", countMST(nVertex, mod));
}
return 0;
}
