定理证明请点这,多看几遍就懂了 模板题点这 题目大意: *一个有n座城市的组成国家,城市1至n编号,其中一些城市之间可以修建高速公路; *需要有选择的修建一些高速公路,从而组成一个交通网络; *计算有多少种方案,使得任意两座城市之间恰好只有一条路径; 模板 : #incl deiostream #incl decstdio #incl decstring #incl decmath #incl dealgorithm #define ll long long sing namespace std; const int maxn=20; int degree[maxn]; 度数矩阵,记录每一个点的度数. 不懂就看下上面那个定理证明. ll a[maxn][maxn]; 矩阵树, 对角线是度数矩阵的每一个数,其余地方为 a[i][j] = a[i][j] - vis[i][j] ; int vis[maxn][maxn]; 临接矩阵, 与v相连就是等于1,否则就是为0.注意是无向边. ll det(int n) 生成树计数:matrix-tree定理 这个是求行列式的精华啊(实质上这个子函数就是用来求行列式的值的!)(所以也适用于求行列式值的题) { ll ret=1; for(int i=2; i=n; i) 计算任意一个n-1阶行列式的值就是答案. { for(int j=i+1; j=n; j){ while(a[j][i]) { ll t=a[i][i]a[j][i]; 如果要模,则这里就一下 for(int k=i; k=n; k) a[i][k]=(a[i][k]-a[j][k]*t); 加一下 for(int k=i; k=n; k) swap(a[i][k],a[j][k]); ret=-ret; } } if(a[i][i]==0) ret rn 0; 图无法联通. ret*=a[i][i]; 加一下 } if(ret0)  可以缩合为 ((ret % p ) + p ) % p ; ret=-ret; ret rn ret; } 这个就是程序的主要函数,计算行列式的值. int main { int tcase; scanf("%d",&tcase); while(tcase--) { memset(degree,0,sizeof(degree)); memset(a,0,sizeof(a)); memset(vis,0,sizeof(vis)); int n,m; scanf("%d%d",&n,&m); int ,v; while(m--) { scanf("%d%d",& ,&v); vis[ ][v]=1; 相连就是1,否则就是0. vis[v][ ]=1; degree[ ]; degree[v]; } for(int i=1;i=n;i){ for(int j=1;j=n;j){ if(i==j) a[i][j] = degree[i]; else a[i][j] -= vis[i][j]; } } printf("%lldn",det(n)); } ret rn 0; } 综合一下,还可以这样写: (这个是在定理上面加强版,把一些步骤直接在缩合在了一起) 灵活点就是在目标矩阵中,为:(对于一些变形题就这样处理). 无向图的基尔霍夫矩阵: 对角线上表示每个点的度数,若ij之间有边则矩阵ij处为-1 无向图的生成树的数目为: 任意一个n-1阶主子式的行列式的绝对值. while(m--) { scanf("%d%d",& ,&v); a[ ][v]=a[v][ ]=-1;  与v相连,所以在目标矩阵中为-1. degree[ ]; degree[v]; } for(int i=1;i=n;i) a[i][i]=degree[i];