BUPT 2017 Summer Training (for 16) #6C

题意

n个点，完全图减去m条边，求生成树个数。

题解

注意可能会给重边。

然后就是生成树计数了。

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 101

#define eps (1e-8)

#define mem(x,v) memset(x,v,sizeof(x))

typedef long long ll;

using namespace std;

int n,m,k;

ll g[N][N];

int sgn(double x){

	return x>eps?1:(x<-eps?-1:0);

}

ll det(int n){

	int i,j,k;

	ll ans=1,t;

	for(i=0;i<n;++i){

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

			while(g[j][i]){

				t=g[i][i]/g[j][i];

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

					g[i][k]-=g[j][k]*t;

				swap(g[i],g[j]);

				ans=-ans;

			}

		if(g[i][i]==0)return 0L;

		ans=ans*g[i][i];

	}

	return ans;

}

int main(){

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

		mem(g,-1);

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

			g[i][i]=0;

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

			int u,v;

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

			--u;--v;//！！！

			g[u][v]=g[v][u]=0;

		}

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

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

				if(g[i][j]){

					++g[i][i];

					++g[j][j];

				}

			}

		printf("%lld\n",det(n-1));

	}

	return 0;

}