专栏首页饶文津的专栏【HDU 4305】Lightning(生成树计数)

【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

题意:

给出n个点的坐标,距离不超过r的点如果中间没有其它点则可以连一条边,最后求生成树的数量,对10007取模。

分析:

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。

有了这个定理,我们要只要构造Kirchhoff矩阵,然后计算行列式就行了,注意要取模。

构造矩阵需要判断一下满足距离不超过r的两点之间是否有其它点,直接三层循环用叉积判断ijk是否共线,如果共线k是否在ij之间。

然后是行列式的计算:

是线性代数的知识,先通过初等变换化成 上三角的行列式,主对角线的积就是行列式的值了。

而初等变换的过程,如果是交换两行,行列式要乘上-1,所以记录一下交换了几次,最后根据奇偶来乘-1。我们要用Cii来消去它下面的数。第i行每个数都要除以Cii,这个过程因为我们是取模的,所以要用逆元,于是提前预处理逆元。

(对于这题我有一个疑惑,如果行列式的值是负数,那么生成树的个数就是它的绝对值,答案不应该是这个绝对值再取模吗,但是它的数据却是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);
    }
}

另外一种求行列式的方法可以不用求逆元,万一mod是非质数就不能用求逆元了,所以这种方法就派上用场了。

#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 分别代...

    desperate633
  • HDU 3078 Network

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

    attack
  • Lake Counting (POJ No.2386)

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

    用户7727433
  • POJ-1088 滑雪 (记忆化搜索,dp)

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

    ShenduCC
  • LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

    ShenduCC
  • LeetCode Weekly Contest 32解题思路

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

    用户1147447
  • 最大子段和问题

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

    我没有三颗心脏

扫码关注云+社区

领取腾讯云代金券