这题真心不错，，刷新了我对matrix-tree定理的认识，
现在我对MT定理的认识是：
可以计算
有向图的每颗外/内向树的边权值的乘积的和
无向图图的每颗生成树的边权值的乘积的和
特别的，当边权为1时，就是生成树的数量
#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define INFLL 0x3f3f3f3f3f3f3f3f #define FIN freopen("input.txt","r",stdin); #define mem(x,y) memset(x,y,sizeof(x)); typedef unsigned long long ULL; typedef long long LL; #define fuck(x) cout<<x<<endl; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef pair<pair<int, int>, int> PIII; typedef pair<int, int> PII; const double eps = 1e-10; const double PI = acos(-1); const int P = 1e9 + 7; const int MX = 333; int n; double mat[MX][MX]; //会改变原来的矩阵，可以先备份一份 double MT(double w[][MX],int n,int g) //g为有向图根节点编号，无向图随便填个 { if(n==1)return 1;//如果只有一个点就是1 //将根节点和0节点互换，注意会改变原先的矩阵 for(int i=0; i<n; i++)swap(w[0][i],w[g][i]); for(int i=0; i<n; i++)swap(w[i][0],w[i][g]); //化为上三角 for(int i=1; i<n; i++) { int t=i; for(int j=i; j<n; j++) if(fabs(w[j][i])>fabs(w[t][i])) { t=j; } if(t!=i) for(int j=i; j<n; j++) swap(w[i][j],w[t][j]); for(int j=i+1; j<n; j++) if(fabs(w[j][i])>eps) { double v=w[j][i]/w[i][i]; for(int k=i; k<=n+1; k++) w[j][k]=w[j][k]-w[i][k]*v; } } double ans=1; for(int i=1; i<n; i++)ans=ans*w[i][i]; return fabs(ans); } int main() { scanf("%d",&n); { double p=1; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { scanf("%lf",&mat[i][j]); if(i==j)continue; if(i<j)if(1-mat[i][j]<eps)p*=eps; else p*=(1-mat[i][j]); if(1-mat[i][j]<eps) mat[i][j]/=eps; else mat[i][j]/=(1-mat[i][j]); mat[i][j]*=-1; } for(int i=0; i<n; i++) { double cnt=0; for(int j=0; j<n; j++)cnt+=mat[i][j]; mat[i][i]=-1*cnt; } double ans=MT(mat,n,0); printf("%.10f\n",ans*p); } return 0; }
