Lightning（生成树计数）

原题： http://acm.hdu.edu.cn/showproblem.php?pid=4305

题意：

n个点，任意两个点之间可以连边当且仅当距离不大于R，并且中间没有其他边。求生成树个数。

解析：

判断中间有没有点可以直接n3for，也可以n2log，枚举每个点为起点，其他的点与之形成的向量用map比较是否存在即可。

连完边就用矩阵树进行n3做就行了。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long

const ll p = 10007;

const int maxn=309;
int x[maxn],y[maxn];

bool f[maxn][maxn];
ll c[maxn][maxn];
ll det(ll n) {
    ll ret=1;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++)
            while(c[j][i]) {
                ll t=c[i][i]/c[j][i];
                for(int k=i; k<n; k++)
                    c[i][k]=(c[i][k]-c[j][k]*t)%p;
                swap(c[i],c[j]);
                ret=-ret;
            }
        if(c[i][i]==0)
            return 0;
        ret=ret*c[i][i]%p;
    }
    return (ret+p)%p;
}
inline void link(int a,int b) {
    f[a][b]=1;
    f[b][a]=1;
}
int fa[maxn];
int fin(int i){return fa[i]==i?i:fa[i]=fin(fa[i]); }
void deal(int n) {
    rep(i,1,n)fa[i]=i;
    memset(c,0,sizeof c);
    int sum=n;
    rep(i,1,n){
        rep(j,i+1,n){
            if(f[i][j]){
                int f1=fin(i),f2=fin(j);
                if(f1!=f2){
                    sum--;
                    fa[f1]=f2;
                }
                c[i-1][j-1]--;
                c[i-1][i-1]++;
                c[j-1][i-1]--;
                c[j-1][j-1]++;
            }
        }
    }
    if(sum>1){
        printf("-1\n");
        return ;
    }
    printf("%lld\n",det(n-1));
}

struct pair_hash
{
    template<class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2>& p) const
    {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ h2;
    }
};

int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        memset(f,0,sizeof f);
        int n,r;
        scanf("%d%d",&n,&r);
        rep(i,1,n) {
            scanf("%d%d",x+i,y+i);
        }
        rep(i,1,n) {
            unordered_map<pair<int,int>,int,pair_hash>M;
            rep(j,1,n) {
                if(i==j)
                    continue;
                int X=x[j]-x[i],Y=y[j]-y[i];
                double L=sqrt(1.0*X*X+1.0*Y*Y);
                if(L>(double)r)
                    continue;
                int gcd=__gcd(X,Y);
                X/=gcd,Y/=gcd;
                if(M.count({X,Y})==0) {
                    M[ {X,Y}]=j;
                } else {
                    int p0=M[ {X,Y}];
                    double L0=sqrt(1.0*(x[p0]-x[i])*(x[p0]-x[i])+1.0*(y[p0]-y[i])*(y[p0]-y[i]));
                    if(L<L0) {
                        M[ {X,Y}]=j;
                    }
                }
            }
            for(auto p:M) {
                link(i,p.second);
            }
        }
        deal(n);
    }
}