題意：給你n個點，如果兩個點的距離小於等於r那麼就連一條邊，讓你求生成樹的個數。
題解：
對於無向圖G，它的Kirchhoff矩陣C定義為它的度數矩陣D減去它的鄰接矩陣A。顯然，這樣的定義滿足剛才描述的性質。
有了Kirchhoff矩陣這個工具，我們可以引入Matrix-Tree定理：
矩陣的規則是：
1、在主對角線上的元素為此節點的度數
2、對於其他位置上的元素Matrix(i,j) { i != j }，
(1) 如果節點i和節點j連通，則Matrix(i,j)的值為-k，其中k值為節點i到節點j的平行邊個數。如果此圖是一個簡單圖，即任意兩點間不存在平行邊，那麼這個值就為-1.
(2) 但如果節點i和節點j根本不連通，則Matrix(i,j)的值為0。
求法：對於一個無向圖G，它的生成樹個數等於其Kirchhoff矩陣任何一個n-1階主子式的行列式的絕對值。所謂n-1階主子式，就是對於任意一個r，將C的第r行和第r列同時刪去後的新矩陣，用Cr表示。復雜度為O(n^3)
AC代碼：
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=302;
const LL mod=10007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-7;
using namespace std;
int a[N][N],mp[N][N];
int n;
double r;
struct node
{
double x,y;
node(){};
node(double a,double b):x(a),y(b){}
void input()
{
scanf("%lf%lf",&x,&y);
}
friend node operator -(const node &a,const node &b)
{
return node(a.x-b.x,a.y-b.y);
}
}p[N];
double dis(node a,node b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool love(int i,int k,int j)
{
double t=(p[i].x-p[k].x)*(p[j].y-p[k].y)-(p[i].y-p[k].y)*(p[j].x-p[k].x);
if(fabs(t-0)>1e-6)
return false;//不在一條直線上
t=(p[i].x-p[k].x)*(p[j].x-p[k].x)+(p[i].y-p[k].y)*(p[j].y-p[k].y);
if(t>=0)
return false;//不在ij中間
return true;
}
int ext_gcd(int a,int b,int &x,int &y)
{
int t,ret;
if(!b)
{
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
int gauss(int r,int c)
{
int i=1,k,j,cnt=1;
for(j=1;j<=c;j++)
{
int id=i;
for(k=i;k<=r;k++)
if(a[k][j]>0)
{
id=k;break;
}
if(a[id][j])
{
if(id!=i)
{
for(k=j;k<=c;k++)
swap(a[i][k],a[id][k]);
}
for(k=i+1;k<=r;k++)
{
if(!a[k][j]) continue;
cnt=(cnt*a[i][j])%mod;
for(int l=c;l>=j;l--)
{
a[k][l]=(a[k][l]*a[i][j]-a[i][l]*a[k][j])%mod;
a[k][l]=(a[k][l]+mod)%mod;
}
}
i++;
}
}
int x,y;
ext_gcd(cnt,mod,x,y);
x=(x%mod+mod)%mod;//x為cnt對mod的逆元
for(i=1;i<=r;i++)
x=(x*a[i][i])%mod;
return (x+mod)%mod;
}
int main()
{
int t,i,j,k,cas;
scanf("%d",&t);
while(t--)
{
scanf("%d%lf",&n,&r);
for(i=1;i<=n;i++)
p[i].input();
memset(a,0,sizeof(a));
memset(mp,0,sizeof(mp));
double rr=r*r;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
if(dis(p[i],p[j])>rr) continue;
int flag=1;
for(k=1;k<=n;k++)
{
if(i==k||j==k) continue;
//這個地方開始用的是運算符重載，結果超時了，改成自己定義就A了
if(love(i,k,j))//k在ij線段的中間
{
flag=0;
break;
}
}
if(flag)
{
mp[i][j]=mp[j][i]=1;
a[i][j]--; a[j][i]--;
a[i][i]++; a[j][j]++;
}
}
/*cout<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",mp[i][j]);
cout<<endl;
}
cout<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",a[i][j]);
cout<<endl;
}*/
int xh=gauss(n-1,n-1);
if(xh==0)
puts("-1");
else
printf("%d\n",xh);
}
return 0;
}
/*
3
3 2
-1 0
0 1
1 0
3 2
-1 0
0 0
1 0
3 1
-1 0
0 1
1 0
*/
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=302;
const LL mod=10007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-7;
using namespace std;
int a[N][N],mp[N][N];
int n;
double r;
struct node
{
double x,y;
node(){};
node(double a,double b):x(a),y(b){}
void input()
{
scanf("%lf%lf",&x,&y);
}
friend node operator -(const node &a,const node &b)
{
return node(a.x-b.x,a.y-b.y);
}
}p[N];
double dis(node a,node b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool love(int i,int k,int j)
{
double t=(p[i].x-p[k].x)*(p[j].y-p[k].y)-(p[i].y-p[k].y)*(p[j].x-p[k].x);
if(fabs(t-0)>1e-6)
return false;//不在一條直線上
t=(p[i].x-p[k].x)*(p[j].x-p[k].x)+(p[i].y-p[k].y)*(p[j].y-p[k].y);
if(t>=0)
return false;//不在ij中間
return true;
}
int ext_gcd(int a,int b,int &x,int &y)
{
int t,ret;
if(!b)
{
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
int gauss(int r,int c)
{
int i=1,k,j,cnt=1;
for(j=1;j<=c;j++)
{
int id=i;
for(k=i;k<=r;k++)
if(a[k][j]>0)
{
id=k;break;
}
if(a[id][j])
{
if(id!=i)
{
for(k=j;k<=c;k++)
swap(a[i][k],a[id][k]);
}
for(k=i+1;k<=r;k++)
{
if(!a[k][j]) continue;
cnt=(cnt*a[i][j])%mod;
for(int l=c;l>=j;l--)
{
a[k][l]=(a[k][l]*a[i][j]-a[i][l]*a[k][j])%mod;
a[k][l]=(a[k][l]+mod)%mod;
}
}
i++;
}
}
int x,y;
ext_gcd(cnt,mod,x,y);
x=(x%mod+mod)%mod;//x為cnt對mod的逆元
for(i=1;i<=r;i++)
x=(x*a[i][i])%mod;
return (x+mod)%mod;
}
int main()
{
int t,i,j,k,cas;
scanf("%d",&t);
while(t--)
{
scanf("%d%lf",&n,&r);
for(i=1;i<=n;i++)
p[i].input();
memset(a,0,sizeof(a));
memset(mp,0,sizeof(mp));
double rr=r*r;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
if(dis(p[i],p[j])>rr) continue;
int flag=1;
for(k=1;k<=n;k++)
{
if(i==k||j==k) continue;
//這個地方開始用的是運算符重載，結果超時了，改成自己定義就A了
if(love(i,k,j))//k在ij線段的中間
{
flag=0;
break;
}
}
if(flag)
{
mp[i][j]=mp[j][i]=1;
a[i][j]--; a[j][i]--;
a[i][i]++; a[j][j]++;
}
}
/*cout<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",mp[i][j]);
cout<<endl;
}
cout<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",a[i][j]);
cout<<endl;
}*/
int xh=gauss(n-1,n-1);
if(xh==0)
puts("-1");
else
printf("%d\n",xh);
}
return 0;
}
/*
3
3 2
-1 0
0 1
1 0
3 2
-1 0
0 0
1 0
3 1
-1 0
0 1
1 0
*/
