uva10766生成树计数(矩阵树定理)

更正了我之前打错的地方，有边的话G[i][j]=-1;

WA了好多次，中间要转成long double才行。。这个晚点更新。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 using namespace std;

 typedef long double ld;

 const int N=;

 const ld eps=1e-;

 int map[N][N];

 ld G[N][N];

 ld myabs(ld x){return x> ? x:-x;}

 ld guass(int n)

 {

     ld ans=;

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

     {

         int r=i;

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

             if(myabs(G[j][i]) > myabs(G[r][i])) r=j;

         if(r!=i)

         {

             for(int j=;j<=n;j++) swap(G[i][j],G[r][j]);

             ans*=-;

         }

         if(myabs(G[i][i])<eps) return ;

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

             for(int k=n;k>=i;k--)

                 G[j][k]-=G[j][i]/G[i][i]*G[i][k];

     }

     for(int i=;i<=n;i++) ans*=G[i][i];

     return myabs(ans);

 }

 int main()

 {

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

     int n,m,k;

     while(scanf("%d%d%d",&n,&m,&k)!=EOF)

     {

         int x,y;

         memset(map,,sizeof(map));

         memset(G,,sizeof(G));

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

         {

             scanf("%d%d",&x,&y);

             map[x][y]=map[y][x]=;

         }

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

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

                 if(!map[i][j])

                 {

                     G[i][j]=-;G[j][i]=-;

                     G[i][i]++;G[j][j]++;

                 }

         printf("%.0lf\n",(double)guass(n-));

     }

     return ;

 }