【概述】

給出一個由 n 個點和 m?條邊構成的簡單無向加權圖，有時需要對生成樹計數或對最小生成樹計數。

當對生成樹計數時，利用基爾霍夫矩陣的?Matrix-Tree 定理即可解決，而對最小生成樹計數時，根據數據范圍的不同，所采用的方法也不同。

關于基爾霍夫矩陣：點擊這里

【生成樹計數】

對于生成樹的計數，一般采用矩陣樹定理(Matrix-Tree 定理)來解決。

Matrix-Tree 定理的內容為：對于已經得出的基爾霍夫矩陣，去掉其隨意一行一列得出的矩陣的行列式，其絕對值為生成樹的個數

因此，對于給定的圖 G，若要求其生成樹個數，可以先求其基爾霍夫矩陣，然后隨意取其任意一個 n-1 階行列式，然后求出行列式的值，其絕對值就是這個圖中生成樹的個數。

LL K[N][N]; LL gauss(int n){//求矩陣K的n-1階順序主子式LL res=1;for(int i=1;i<=n-1;i++){//枚舉主對角線上第i個元素for(int j=i+1;j<=n-1;j++){//枚舉剩下的行while(K[j][i]){//輾轉相除int t=K[i][i]/K[j][i];for(int k=i;k<=n-1;k++)//轉為倒三角K[i][k]=(K[i][k]-t*K[j][k]+MOD)%MOD;swap(K[i],K[j]);//交換i、j兩行res=-res;//取負}}res=(res*K[i][i])%MOD;}return (res+MOD)%MOD; } int main(){int n,m;scanf("%d%d",&n,&m);memset(K,0,sizeof(K));for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);K[x][x]++;K[y][y]++;K[x][y]--;K[y][x]--;}printf("%lld\n",gauss(n));return 0; }

【最小生成樹計數】

根據給出的 n、m 的數據范圍，最小生成樹的計數分為簡化版、加強版。

最小生成樹的計數的核心為 MST 的以下兩條性質：

• 每種權值的邊的數量是固定的
• 不同的生成樹中，某一種權值的邊任意加入需要的數量后，形成的聯通塊狀態是相同的

1.簡化版

當每種權值的邊不超過 10 條時，利用?dfs，暴力枚舉即可解決，時間復雜度為?

根據最小生成樹的性質，先統計出每種權值需要的邊的條數 cnt

然后進行 dfs，枚舉第?i?種權值的邊選擇哪 cnt??條，然后根據乘法原理來統計答案

需要注意的是，為了能夠快速分開連通塊，并查集中不能使用路徑壓縮

struct Edge {int x,y;int dis;bool operator < (const Edge &rhs)const{return dis<rhs.dis;} } edge[N]; struct build {int l,r;int cnt; } a[N]; int tot; int n,m; int father[N]; int sum;int Find(int x) {if(father[x]!=x)return Find(father[x]);return father[x]; } void dfs(int x,int now,int num) {if(now==a[x].r+1) {if(num==a[x].cnt)//選指定的條數sum++;return ;}int fx=Find(edge[now].x);int fy=Find(edge[now].y);if(fx!=fy) {//選father[fx]=fy;dfs(x,now+1,num+1);father[fx]=fx;father[fy]=fy;}dfs(x,now+1,num);//不選 } int Kruskal() {sort(edge+1,edge+m+1);for(int i=1; i<=n; i++)father[i]=i;int cnt=0;for(int i=1; i<=m; i++) {if(edge[i].dis!=edge[i-1].dis) {tot++;a[tot].l=i;a[tot-1].r=i-1;}int x=Find(edge[i].x);int y=Find(edge[i].y);if(x!=y) {father[y]=x;a[tot].cnt++;cnt++;}}a[tot].r=m;return cnt; } int main() {scanf("%d%d",&n,&m);int x,y,z;for(int i=1; i<=m; i++)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].dis);int num=Kruskal();if(num!=n-1) {printf("0");return 0;}else{for(int i=1; i<=n; i++)father[i]=i;int res=1;for(int i=1; i<=tot; i++) {sum=0;dfs(i,a[i].l,0);res=res*sum;for(int j=a[i].l; j<=a[i].r; j++) {int x=Find(edge[j].x);int y=Find(edge[j].y);if(x!=y)father[y]=x;}}printf("%d",res);}return 0; }

2.加強版

當每種權值的邊不超過 100 條，需要利用 Matrix-Tree 定理，時間復雜度為?

根據 MST 的性質，枚舉樹邊的權值 i，將權值不是 i 的樹邊都加入到圖中然后進行縮點。將權值是 i 的原圖中的邊，在縮點后構造基爾霍夫矩陣，再利用?Matrix-Tree 定理求出方案數。

最終答案根據乘法原理進行計算即可。

struct Edge {int x,y;int dis;bool operator < (const Edge &rhs) const {return dis<rhs.dis;} } edge[N],tr[N]; int n,m; int father[N]; int G[N][N]; int tot,bel[N],val[N]; int Find(int x) {if(father[x]!=x)return father[x]=Find(father[x]);return x; } int Gauss(int n) {int res=1;for(int i=1; i<=n; i++) {for(int k=i+1; k<=n; k++) {while(G[k][i]) {int d=G[i][i]/G[k][i];for(int j=i; j<=n; j++)G[i][j]=(G[i][j]-1LL*d*G[k][j]%MOD+MOD)%MOD;swap(G[i],G[k]);res=-res;}}res=1LL*res*G[i][i]%MOD,res=(res+MOD)%MOD;}return res; } int Kruskal() {sort(edge+1,edge+m+1);for(int i=1; i<=n; i++)father[i]=i;int cnt=0;for(int i=1; i<=m; i++) {int fu=Find(edge[i].x);int fv=Find(edge[i].y);if(fu==fv)continue;father[fu]=fv,tr[++cnt]=edge[i];if(edge[i].dis!=val[tot])val[++tot]=edge[i].dis;}return cnt; } void addTreeEdge(int v) {for(int i=1; i<n&&tr[i].dis!=v; i++){int x=tr[i].x;int y=tr[i].y;father[Find(x)]=Find(y);}for(int i=n-1; i&&tr[i].dis!=v; i--){int x=tr[i].x;int y=tr[i].y;father[Find(x)]=Find(y);} } void rebuild(int v) {memset(G,0,sizeof(G));for(int i=1; i<=m; i++){if(edge[i].dis==v){int x=bel[edge[i].x];int y=bel[edge[i].y];G[x][y]--;G[y][x]--;G[x][x]++;G[y][y]++;}} } int main() {scanf("%d%d",&n,&m);for(int i=1; i<=m; i++)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].dis);int cnt=Kruskal();if(cnt!=n-1) {printf("0\n");}else{int res=1;for(int i=1; i<=tot; i++) {for(int i=1; i<=n; i++)father[i]=i;addTreeEdge(val[i]);int blo=0;for(int i=1; i<=n; i++)if(Find(i)==i)bel[i]=++blo;for(int i=1; i<=n; i++)bel[i]=bel[Find(i)];rebuild(val[i]);res=1LL*res*Gauss(blo-1)%MOD;}printf("%d\n",res);}return 0; }

?

總結

以上是生活随笔為你收集整理的图论 —— 生成树 —— 生成树计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。