差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:矩阵树定理 [2020/07/24 13:29]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:矩阵树定理 [2020/07/27 22:59] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:jxm_矩阵树定理被移动并更名为2020-2021:teams:legal_string:jxm2001:矩阵树定理
@@ 行 1: / 行 1: @@
-====== 矩形树定理 ======
+====== 矩阵树定理 ======
 ===== 算法简介 =====
-一种生成树的计算定理，时间复杂度 $O\left(n^3\right)$。
+一种生成树的计数定理，时间复杂度 $O\left(n^3\right)$。
 ===== 算法实现 =====
@@ 行 41: / 行 41: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAX_size=305,mod=1e9+7;
 struct Matrix{
@@ 行 169: / 行 122: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAX_size=55;
 const double eps=1e-8;
@@ 行 320: / 行 226: @@
 考虑在辗转相除过程中维护系数，即维护 $i'=ai+bj,j'=ci+dj$，可以将计算行列式复杂度降为 $O(n^3)$。
-最后发现每次消元中 $n=$ 连通块个数 $=$ 最小生成树中边权为 $w$ 的边的个数 $\text{cnt}_w$，于是总时间复杂度为
+最后发现每次消元中 $n=$ 连通块个数 $=$ 最小生成树 $T$ 中边权为 $w$ 的边的个数 $\text{cnt}_w$，于是总时间复杂度为
-$O\left(\sum_{w\in T}\text{cnt}_w^3\right)=O(n^3)$。
+\begin{equation}O\left(\sum_{w\in T}\text{cnt}_w^3\right)=O(|T|^3)=O(n^3)\end{equation}
+<hidden 查看代码>
+<code cpp>
+const int MAX_size=105,MAXN=105,MAXM=1e3+5,mod=31011;
+struct Matrix{
+	int ele[MAX_size][MAX_size];
+};
+int sp_gcd(int a,int b,pair<int,int> &x,pair<int,int> &y){
+	int sign=1;
+	x.first=1,x.second=0,y.first=0,y.second=1;
+	while(b){
+		x.first=(x.first-a/b*y.first)%mod;
+		x.second=(x.second-a/b*y.second)%mod;
+		a%=b;
+		swap(x,y);
+		swap(a,b);
+		sign=-sign;
+	}
+	return sign;
+}
+int det(Matrix a,int n,int mod){
+	int ans=1;
+	_rep(i,2,n){
+		int pos=i;
+		_rep(j,i,n)if(a.ele[j][i]){pos=j;break;}
+		if(!a.ele[pos][i])return 0;
+		if(pos!=i){_rep(j,i,n) swap(a.ele[i][j],a.ele[pos][j]);ans=mod-ans;}
+		pair<int,int> x,y;
+		int t1,t2;
+		_rep(j,i+1,n){
+			ans*=sp_gcd(a.ele[i][i],a.ele[j][i],x,y);
+			_rep(k,i,n){
+				t1=a.ele[i][k],t2=a.ele[j][k];
+				a.ele[i][k]=(t1*x.first+t2*x.second)%mod;
+				a.ele[j][k]=(t1*y.first+t2*y.second)%mod;
+			}
+		}
+		ans=ans*a.ele[i][i]%mod;
+	}
+	return (ans+mod)%mod;
+}
+struct Edge{
+	int u,v,w;
+	bool operator < (const Edge &b)const{
+		return w<b.w;
+	}
+}edge[MAXM];
+bool vis[MAXM];
+int p[MAXN],block_id[MAXN],block_cnt;
+int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
+int main()
+{
+	int n=read_int(),m=read_int(),u,v,w;
+	Matrix X;
+	_rep(i,1,m)
+	edge[i].u=read_int(),edge[i].v=read_int(),edge[i].w=read_int();
+	sort(edge+1,edge+1+m);
+	_rep(i,1,n)
+	p[i]=i;
+	block_cnt=n;
+	for(int i=1;i<=m&&block_cnt>1;i++){
+		int x=Find(edge[i].u),y=Find(edge[i].v);
+		if(x!=y)
+		p[x]=y,vis[i]=true,block_cnt--;
+	}
+	if(block_cnt>1){
+		puts("0");
+		return 0;
+	}
+	int ans=1;
+	for(int pos1=1,pos2=1;pos1<=m;pos1=pos2){
+		_rep(i,1,n)p[i]=i,block_id[i]=0;
+		_rep(i,1,m){
+			if(vis[i]&&edge[i].w!=edge[pos1].w)
+			p[Find(edge[i].u)]=Find(edge[i].v);
+		}
+		block_cnt=0;
+		_rep(i,1,n){
+			if(!block_id[Find(i)])block_id[Find(i)]=++block_cnt;
+			block_id[i]=block_id[Find(i)];
+		}
+		_rep(i,1,block_cnt)_rep(j,1,block_cnt)X.ele[i][j]=0;
+		while(edge[pos2].w==edge[pos1].w){
+			u=block_id[edge[pos2].u],v=block_id[edge[pos2].v];
+			X.ele[u][v]--;X.ele[v][u]--;
+			X.ele[u][u]++;X.ele[v][v]++;
+			pos2++;
+		}
+		ans=ans*det(X,block_cnt,mod)%mod;
+	}
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具