題意

某圖有n(1<=n<=100)個點，m(0<=m<=1000)條邊，求該圖的“最小生成樹的個數(shù)%p”(1<=p<=1000000000)。

題解

需要結(jié)合Matrix-Tree定理和Kruskal算法。

首先將所有的邊按照邊長從小到大排序，相同長度的邊分為一組。從長度小的組開始處理。

對于每組邊，用一個并查集（disSet）表示加入這組邊之前的連通性，另一個并查集（tempSet）表示加入這組邊之后的連通性。

將disSet中每個連通分量視為一個點，得到一個新的圖G。

再將圖G根據(jù)tempSet分為不同的連通分量，將其每個連通分量視為一個圖，由Matrix-Tree定理計算通過該組邊可以得到的生成樹的個數(shù)。然后將所有得到的個數(shù)累乘即可。

注意計算過程中對p取模，另外此題將只有一個點的圖的生成樹個數(shù)視為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];//計算最小生成樹個數(shù)的函數(shù) 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;//當(dāng)邊的長度不同時退出，即一組一組地處理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; }

總結(jié)

以上是生活随笔為你收集整理的HDU_4408的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。