一、生成树计数：
例①：Highways SPOJ - HIGH
In some countries building highways takes a lot of time… Maybe that’s because there are many possiblities to construct a network of highways and engineers can’t make up their minds which one to choose. Suppose we have a list of cities that can be connected directly. Your task is to count how many ways there are to build such a network that between every two cities there exists exactly one path. Two networks differ if there are two cities that are connected directly in the first case and aren’t in the second case. At most one highway connects two cities. No highway connects a city to itself. Highways are two-way.
Input
The input begins with the integer t, the number of test cases (equal to about 1000). Then t test cases follow. The first line of each test case contains two integers, the number of cities (1<=n<=12) and the number of direct connections between them. Each next line contains two integers a and b, which are numbers of cities that can be connected. Cities are numbered from 1 to n. Consecutive test cases are separated with one blank line.
Output
The number of ways to build the network, for every test case in a separate line. Assume that when there is only one city, the answer should be 1. The answer will fit in a signed 64-bit integer.
Example
Sample input:
4
4 5
3 4
4 2
2 3
1 2
1 3
2 1
2 1
1 0
3 3
1 2
2 3
3 1
Sample output:
8
1
1
3
题意：求生成树个数。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=20;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
int g[maxn][maxn],n,m;
double a[maxn][maxn];
int sgn(double x)
{
if(abs(x)<eps) return 0;
if(x>0) return 1;
return -1;
}
double Gu(int n)
{
double res=1;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(sgn(a[j][i])!=0)
{
if(j!=i)
{
res*=-1;
for(int k=i;k<=n;k++)
swap(a[i][k],a[j][k]);
}
break;
}
}
if(sgn(a[i][i])==0) return 0;
res=res*a[i][i];
for(int j=i+1;j<=n;j++)
{
double tmp=a[j][i]/a[i][i];
for(int k=i;k<=n;k++)
a[j][k]-=tmp*a[i][k];
}
}
return abs(res);
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int x,y;
memset(g,0,sizeof(g));
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&g[i][j])
{
a[i][i]++;
a[i][j]=-1;
}
}
}
printf("%.0f\n",Gu(n-1));
}
return 0;
}
不用浮点数：
可用最小公倍数消元或者辗转相除法消元：
但是容易造成中间结果溢出。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=20;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
int g[maxn][maxn],n,m;
int a[maxn][maxn];
int Gu(int n)
{
int res=1;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(a[j][i]!=0)
{
if(j!=i)
{
res=-res;
for(int k=i;k<=n;k++)
swap(a[i][k],a[j][k]);
}
break;
}
}
if(a[i][i]==0) return 0;
for(int j=i+1;j<=n;j++)
{
while(a[j][i])
{
int t=a[i][i]/a[j][i];
for(int k=i;k<=n;k++)
a[i][k]-=t*a[j][k];
for(int k=i;k<=n;k++)
swap(a[i][k],a[j][k]);
res=-res;
}
}
res=res*a[i][i];
}
return abs(res);
}
signed main(void)
{
int t;
scanf("%lld",&t);
while(t--)
{
int x,y;
memset(g,0,sizeof(g));
memset(a,0,sizeof(a));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&x,&y);
g[x][y]=g[y][x]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&g[i][j])
{
a[i][i]++;
a[i][j]=-1;
}
}
}
printf("%lld\n",Gu(n-1));
}
return 0;
}
例②：Lightning HDU - 4305 ：
图并不好复制。。。
题意：
给出n个点，给出R，两点距离不大于R而且两点之间没其他点阻碍，就可以建一条边，问可以形成多少棵生成树，如果没有，输出-1，否则，输出（生成树个数 mod 10007）
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=320;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
const int mod=10007;
int g[maxn][maxn],n,r;
int a[maxn][maxn];
struct Point
{
int x,y;
Point(){}
Point(int a,int b)
{
x=a,y=b;
}
void input(void)
{
scanf("%lld%lld",&x,&y);
}
Point operator - (const Point &b) const
{
return Point(x-b.x,y-b.y);
}
int operator ^ (const Point &b) const
{
return x*b.y-y*b.x;
}
int operator * (const Point &b) const
{
return x*b.x+y*b.y;
}
int dis2(const Point &b)const
{
return (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
}
}p[maxn];
struct Line
{
Point s,e;
Line(){}
Line(const Point &a,const Point &b)
{
s=a,e=b;
}
int len2(void)
{
return s.dis2(e);
}
bool p_is_on_seg(const Point &p)
{
return ((p-s)^(e-s))==0&&((p-s)*(p-e))<=0;
}
};
//ax=1(mod m)
int inv(int a,int m)
{
if(a==1) return 1;
return inv(m%a,m)*(m-m/a)%m;
}
int Gu(int n)
{
int res=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
a[i][j]=(a[i][j]%mod+mod)%mod;
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(a[j][i]!=0)
{
if(j!=i)
{
res=-res;
res=(res%mod+mod)%mod;
for(int k=i;k<=n;k++)
swap(a[i][k],a[j][k]);
}
break;
}
}
if(a[i][i]==0) return -1;
res=res*a[i][i]%mod;
for(int j=i+1;j<=n;j++)
{
int t=a[j][i]*inv(a[i][i],mod)%mod;
for(int k=i;k<=n;k++)
a[j][k]=((a[j][k]-t*a[i][k])%mod+mod)%mod;
}
}
return (res%mod+mod)%mod;
}
bool check(int a,int b)
{
for(int k=1;k<=n;k++)
{
if(k==a||k==b) continue;
if(Line(p[a],p[b]).p_is_on_seg(p[k])) return false;
}
return true;
}
signed main(void)
{
int t;
scanf("%lld",&t);
while(t--)
{
memset(g,0,sizeof(g));
memset(a,0,sizeof(a));
scanf("%lld%lld",&n,&r);
for(int i=1;i<=n;i++)
p[i].input();
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(p[i].dis2(p[j])>r*r) continue;
if(check(i,j))
g[i][j]=g[j][i]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&g[i][j])
{
a[i][i]++;
a[i][j]=-1;
}
}
}
printf("%lld\n",Gu(n-1));
}
return 0;
}
二、最小生成树计数：
洛谷：P4208 [JSOI2008]最小生成树计数：
题目描述
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
输入格式
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。
接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。
数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
输出格式
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
输入输出样例
输入 #1 复制
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
输出 #1 复制
8
说明/提示
说明 1<=n<=100; 1<=m<=1000;1≤ci≤1e9
31011不是质数，不是质数，不是质数
一定要到处都无脑取模。。。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=110;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
const int mod=31011;//这个不是质数
int n,m;
int a[maxn][maxn];
//复杂度是 n*n*n*logn的
//有n*n*n的。。我不会。
int Gu(int n)
{
int res=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
a[i][j]=(a[i][j]%mod+mod)%mod;
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(a[j][i]!=0)
{
if(j!=i)
{
res=-res;
res=(res%mod+mod)%mod;
for(int k=i;k<=n;k++)
swap(a[i][k],a[j][k]);
}
break;
}
}
if(a[i][i]==0) return 0;
for(int j=i+1;j<=n;j++)
{
while(a[j][i])
{
int t=a[i][i]/a[j][i];
for(int k=i;k<=n;k++)
a[i][k]=((a[i][k]-t*a[j][k])%mod+mod)%mod;
for(int k=i;k<=n;k++)
swap(a[i][k],a[j][k]);
res=-res;
res=(res%mod+mod)%mod;
}
}
res=(res*a[i][i]%mod+mod)%mod;
}
return (res%mod+mod)%mod;
}
struct node
{
int x,y,z;
node(){}
node(int a,int b,int c)
{
x=a,y=b,z=c;
}
friend bool operator <(const node &a,const node &b)
{
return a.z<b.z;
}
}e[maxn*10],b[maxn*10];//原图上的边，最小生成树上的边
vector<node>vc[maxn*10];//相同边权的边
int f[maxn],ff[maxn];
bool ha[maxn*10];
int fi(int x)
{
if(f[x]!=x)
f[x]=fi(f[x]);
return f[x];
}
signed main(void)
{
int ans=1;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].z);
sort(e+1,e+m+1);
for(int i=1;i<=n;i++)
f[i]=i;
e[0].z=0;
int cnt1=0,cnt2=0;
for(int i=1;i<=m;i++)
{
int xx=fi(e[i].x),yy=fi(e[i].y);
if(e[i].z!=e[i-1].z) cnt1++;
vc[cnt1].push_back(e[i]);
if(xx==yy) continue;
f[xx]=yy;
ha[cnt1]=true;
b[++cnt2]=e[i];
b[cnt2].z=cnt1;
}
if(cnt2!=n-1)
{
printf("0\n");
return 0;
}
for(int i=1;i<=cnt1;i++)
{
if(!ha[i]) continue;//不在最小生成树中
for(int j=1;j<=n;j++)
f[j]=j;
int nown=0;
for(int j=1;j<=cnt2;j++)
{
if(b[j].z==i) continue;
int xx=fi(b[j].x),yy=fi(b[j].y);
f[xx]=yy;
}
for(int j=1;j<=n;j++)
if(f[j]==j) ff[j]=++nown;
for(int j=1;j<=n;j++)
ff[j]=ff[fi(j)];
memset(a,0,sizeof(a));
for(int j=0;j<vc[i].size();j++)
{
int xx=ff[vc[i][j].x],yy=ff[vc[i][j].y];
a[xx][xx]++,a[yy][yy]++;
a[xx][yy]--,a[yy][xx]--;
}
ans=ans*Gu(nown-1)%mod;
}
printf("%lld\n",ans);
return 0;
}
京公网安备 11010502036488号