『算法-ACM 竞赛-图论』生成树计数模板

图论–生成树计数模板

bool zero(double a)
{
    return a>-eps && a<eps;
}
double Gauss()
{
    double mul,Result=1;
    int i,j,k,b[n];
    for(i=0;i<n;i++) b[i]=i;
    for(i=0;i<n;i++){
        if(zero(a[b[i]][i]))
            for(j=i+1;j<n;j++)
                if(!zero(a[b[j]][i])) { swap(b[i],b[j]); Result*=-1; break;  }
        Result*=a[b[i]][i];
        for(j=i+1;j<n;j++)
            if(!zero(a[b[j]][i])){
                mul=a[b[j]][i]/a[b[i]][i];
                for(k=i;k<n;k++)
                    a[b[j]][k]-=a[b[i]][k]*mul;
            }
    }
    return Result;
}