# 【HDU 4305】Lightning（生成树计数）

Problem Description

There are N robots standing on the ground (Don't know why. Don't know how).

Suddenly the sky turns into gray, and lightning storm comes! Unfortunately, one of the robots is stuck by the lightning!

So it becomes overladen. Once a robot becomes overladen, it will spread lightning to the near one.

The spreading happens when:    Robot A is overladen but robot B not.   The Distance between robot A and robot B is no longer than R.   No other robots stand in a line between them. In this condition, robot B becomes overladen.  We assume that no two spreading happens at a same time and no two robots stand at a same position.

The problem is: How many kind of lightning shape if all robots is overladen? The answer can be very large so we output the answer modulo 10007. If some of the robots cannot be overladen, just output -1.

Input

There are several cases. The first line is an integer T (T < = 20), indicate the test cases. For each case, the first line contains integer N ( 1 < = N < = 300 ) and R ( 0 < = R < = 20000 ), indicate there stand N robots; following N lines, each contains two integers ( x, y ) ( -10000 < = x, y < = 10000 ), indicate the position of the robot.

Output

One line for each case contains the answer.

Sample Input

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

Sample Output

3

1

-1

## 分析：

Matrix-Tree定理：Kirchhoff矩阵任意n-1阶子矩阵的行列式的绝对值就是无向图的生成树的数量。

Kirchhoff矩阵的定义是度数矩阵-邻接矩阵。

1、G的度数矩阵D[G]：n*n的矩阵，Dii等于Vi的度数，其余为0。 2、G的邻接矩阵A[G]：n*n的矩阵， Vi、Vj之间有边直接相连，则 Aij=1，否则为0。

（对于这题我有一个疑惑，如果行列式的值是负数，那么生成树的个数就是它的绝对值，答案不应该是这个绝对值再取模吗，但是它的数据却是MOD-绝对值。比如行列式是-3，生成树应该是3，题目的正确答案却是10004）

```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int M=10007;
const int N=301;
int inv[M],mat[N][N];
void init(){//求逆元
inv[1]=1;
for(int i=2;i<M;i++)
inv[i]=(M-M/i)*inv[M%i]%M;
}
int det(int c[][N],int n){//求矩阵c的n阶顺序主子式的绝对值
int i,j,k,w=0,ans=1;
for(i=0;i<n;i++)
for(j=0;j<n;j++) c[i][j]=(c[i][j]%M+M)%M;
for(i=0;i<n;i++){
for(j=i;j<n;j++)//找出第i行起第i列不为0的行
if(c[i][j])break;
if(i!=j)
swap(c[i],c[j]);
ans=ans*c[i][i]%M;
for(j=i+1;j<n;j++)//第j行第i列变为0
for(k=n;k>i;k--)//该行每列减去第i列的值*d
c[j][k]=(c[j][k]-c[i][k]*inv[c[i][i]]%M*c[j][i]%M+M)%M;
}
return ans;
}
struct point{
int x,y;
}p[N];
int same(point a,point b,point c){//判断是否共线
return (a.x-c.x)*(b.y-c.y)==(b.x-c.x)*(a.y-c.y)
&&min(a.x,c.x)<=b.x&&max(a.x,c.x)>=b.x
&&min(a.y,c.y)<=b.y&&max(a.y,c.y)>=b.y;
}
int main(){
init();
int t,n,r;
scanf("%d",&t);
while(t--){
memset(mat,0,sizeof mat);
scanf("%d%d",&n,&r);
for(int i=0;i<n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y))<=r){//距离不大于r
int ok=1;
for(int k=0;k<n;k++)
if(k!=i&&k!=j&&same(p[i],p[k],p[j]))
ok=0;
if(ok){//构造Kirchhoff矩阵
mat[i][j]=mat[j][i]=-1;
mat[i][i]++;mat[j][j]++;
}
}
int ans=det(mat,n-1);
printf("%d\n",ans?ans:-1);
}
}```

```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int M=10007;
const int N=301;
int mat[N][N];
int det(int c[][N],int n){
int i,j,k,t,ret=1;
for(i=0;i<n;i++)
for(j=0;j<n;j++) c[i][j]%=M;
for(i=0; i<n; i++){
for(j=i+1; j<n; j++)
while(c[j][i])
{
t=c[i][i]/c[j][i];//类似辗转相除
for(k=i; k<n; k++)
c[i][k]=(c[i][k]-c[j][k]*t)%M;
swap(c[i],c[j]);
ret=-ret;
}
if(c[i][i]==0)
return 0L;
ret=ret*c[i][i]%M;
}
return (ret+M)%M;
}
struct point{
int x,y;
}p[N];
int same(point a,point b,point c){
return (a.x-c.x)*(b.y-c.y)==(b.x-c.x)*(a.y-c.y)
&&min(a.x,c.x)<=b.x&&max(a.x,c.x)>=b.x
&&min(a.y,c.y)<=b.y&&max(a.y,c.y)>=b.y;
}
int main(){
int t,n,r;
scanf("%d",&t);
while(t--){
memset(mat,0,sizeof mat);
scanf("%d%d",&n,&r);
for(int i=0;i<n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y))<=r){
int ok=1;
for(int k=0;k<n;k++)
if(k!=i&&k!=j&&same(p[i],p[k],p[j]))
ok=0;
if(ok){
mat[i][j]=mat[j][i]=-1;
mat[i][i]++;mat[j][j]++;
}
}
int ans=det(mat,n-1);
printf("%d\n",ans?ans:-1);
}
}```

0 条评论

• ### 【CodeForces 730H】Car Repair Shop

模拟，先看从s[i]时刻开始修理，和之前i-1个是否冲突。如果冲突，就枚举每个s[j]+d[j]时刻开始，看是否冲突，再从中选择最小的时刻。

• ### 「CodeForces - 598B」Queries on a String

字符串s（1 ≤ |s| ≤ 10 000），有m（1 ≤ m ≤ 300）次操作，每次给l,r,k，代表将r位置插入l位置前，执行k（1 ≤ k ≤ 1 00...

• ### 【POJ 3321】Apple Tree

有n个节点以1为根节点的树，给你树的边关系u-v，一开始每个节点都有一个苹果，接下来有两种操作，C x改变节点x的苹果状态，Q x查询x为根的树的所有苹果个数。

• ### LeetCode 75. Sort Colors题目分析

给定一个包含红，白，蓝且长度为 n 的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0，1 和 2 分别代...

• ### HDU 3078 Network

Problem Description The ALPC company is now working on his own network system,...

• ### Lake Counting （POJ No.2386）

题意：有一个M*N的圈子，雨后有积水，然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

• ### POJ-1088 滑雪 （记忆化搜索，dp）

滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

• ### LeetCode Weekly Contest 32解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 最大子段和问题

问题描述： 给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大，或者求出最大的这个和。如果该序列的...