UVa 10766 Organising the Organisation（矩阵树定理）

题意：

给出n, m, k。表示n个点，其中m条边不能直接连通，求生成树个数。

思路：

这也算个裸题，把可以连接的边连接起来，然后矩阵树计算一下即可。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,ll> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 int n,m,root;

 int unable[maxn][maxn];

 long double C[maxn][maxn];

 long double Gauss()

 {

     for(int k=; k<=n; k++)  //k表示当前行数，因为行数与列数一样，所以这里k也代表了列数

     {

         int max_r=k;

         for(int i=k+;i<=n;i++)

             if(fabs(C[i][k])>fabs(C[max_r][k]))  max_r=i;

         if(C[max_r][k]==)  return ;  //有一列为0,行列式的值必为0

         if(max_r!=k)

         {

             for(int j=k;j<=n;j++)

                 swap(C[k][j],C[max_r][j]);

         }

         for(int i=k+;i<=n;i++)

         {

             long double tmp=C[i][k]/C[k][k];

             for(int j=k;j<=n;j++)

                 C[i][j]-=tmp*C[k][j];

         }

     }

     long double ans=;

     for(int i=;i<=n;i++)  ans*=C[i][i];  //化为三角阵后计算主对角线元素乘积

     ans=fabs(ans);

     return ans;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     while(~scanf("%d%d%d",&n,&m,&root))

     {

         memset(unable,,sizeof(unable));

         memset(C,,sizeof(C));

         for(int i=;i<m;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             unable[u][v]=unable[v][u]=;

         }

         for(int i=;i<=n;i++)

         {

             for(int j=i+;j<=n;j++)

             {

                 if(!unable[i][j])

                 {

                     C[i][i]++; C[j][j]++;

                     C[i][j]=C[j][i]=-;

                 }

             }

         }

         n--;

         printf("%.0Lf\n",Gauss());  //%.Lf codeblocks可能不能正确输出，可以用VS测试

     }

     return ;

 }