HDU 4305 Lightning Matrix Tree定理

题目链接:https://vjudge.net/problem/HDU-4305

解法:首先是根据两点的距离不大于R,而且中间没有点建立一个图。之后就是求生成树计数了。

Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前,我们首先明确几个概念:

1、G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当i≠j时,dij=0;当i=j时,dij等于vi的度数。

2、G的邻接矩阵A[G]也是一个n*n的矩阵, 并且满足:如果vi、vj之间有边直接相连,则aij=1,否则为0。

我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G],则Matrix-Tree定理可以描述为:G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式,就是对于r(1≤r≤n),将C[G]的第r行、第r列同时去掉后得到的新矩阵,用Cr[G]表示。

#include <bits/stdc++.h>
using namespace std;
struct Point{
    int x,y;
    Point(int _x = 0, int _y = 0){
        x = _x;
        y = _y;
    }
    Point operator -(const Point &b) const{
        return Point(x-b.x,y-b.y);
    }
    int operator ^(const Point &b) const{
        return x*b.y-y*b.x;
    }
    void input(){
        scanf("%d %d", &x,&y);
    }
};
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s, Point _e){
        s = _s;
        e = _e;
    }
};
bool onSeg(Point P, Line L){
    return ((L.s-P)^(L.e-P))==0 && (P.x-L.s.x)*(P.x-L.e.x)<=0 && (P.y-L.s.y)*(P.y-L.e.y)<=0;
}
int getDis(Point a, Point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
const int mod = 10007;
long long inv(long long a, long long m){
    if(a==1) return 1;
    return inv(m%a,m)*(m-m/a)%m;
}
struct Matrix{
    int mat[330][330];
    void init(){
        memset(mat,0,sizeof(mat));
    }
    int det(int n){
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                mat[i][j] = (mat[i][j]%mod+mod)%mod;
        int res=1;
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(mat[j][i]!=0){
                    for(int k=i; k<n; k++){
                        swap(mat[i][k], mat[j][k]);
                    }
                    if(i != j)
                        res = (-res+mod)%mod;
                    break;
                }
            }
            if(mat[i][i] == 0){
                res = -1;
                break;
            }
            for(int j=i+1; j<n; j++){
                int mul = (mat[j][i]*inv(mat[i][i],mod))%mod;
                for(int k=i; k<n; k++){
                    mat[j][k] = (mat[j][k]-(mat[i][k]*mul)%mod+mod)%mod;
                }
            }
            res = (res * mat[i][i])%mod;
        }
        return res;
    }
};
int g[330][330];
Point p[330];
int n, R;
bool check(int k1, int k2){
    if(getDis(p[k1], p[k2]) > R*R) return false;
    for(int i=0; i<n; i++){
        if(i!=k1&&i!=k2){
            if(onSeg(p[i],Line(p[k1],p[k2]))){
                return false;
            }
        }
    }
    return true;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n,&R);
        for(int i=0; i<n; i++) p[i].input();
        memset(g, 0, sizeof(g));
        for(int i=0; i<n; i++)
            for(int j=i+1; j<n; j++)
                if(check(i,j))
                    g[i][j] = g[j][i] = 1;
        Matrix ret;
        ret.init();
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(i!=j&&g[i][j]){
                    ret.mat[i][j]=-1;
                    ret.mat[i][i]++;
                }
        printf("%d\n", ret.det(n-1));
    }
    return 0;
}
时间: 09-05

HDU 4305 Lightning Matrix Tree定理的相关文章

@算法 - [email&#160;protected] matrix - tree 定理(矩阵树定理)

目录 @0 - 参考资料@ @0.5 - 你所需要了解的线性代数知识@ @1 - 定理主体@ @证明 part - [email protected] @证明 part - [email protected] @证明 part - [email protected] @证明 part - 4@ @2 - 一些简单的推广@ @3 - 例题与应用@ @0 - 参考资料@ MoebiusMeow 的讲解(超喜欢这个博主的!) 网上找的另外一篇讲解 @0.5 - 你所需要了解的线性代数知识@ 什么是矩阵

hdu 4305 Lightning 生成树计数

Matrix-Tree定理 对于一个n个顶点的无向图G 度矩阵D:设i顶点的度数为du[i],则D[i][i]=du[i] 邻接矩阵A:若i和j之间有边,则A[i][j]=1,否则为0 Kirchhoff矩阵C:C=D-A Matrix-Tree定理:对于一个无向图G,它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值. 例题 题目链接:hdu 4305 思路:先按要求建图,再求出Kirchhoff矩阵C,最后求C的任何一个n-1阶行列式的绝对值 #include<

矩阵树定理(Matrix Tree)学习笔记

如果不谈证明,稍微有点线代基础的人都可以在两分钟内学完所有相关内容.. 行列式随便找本线代书看一下基本性质就好了. 学习资源: https://www.cnblogs.com/candy99/p/6420935.html http://blog.csdn.net/Marco_L_T/article/details/72888138 首先是行列式对几个性质(基本上都是用数学归纳法证): 1.交换两行(列),行列式取相反数 2.由1.得若存在两行(列)完全相同则行列式为0 3.上(下)三角行列式即主

hdu 4305 生成树奇数问题

Lightning Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1457    Accepted Submission(s): 469 Problem Description There are N robots standing on the ground (Don't know why. Don't know how). Sudd

HDU 2489 Minimal Ratio Tree(数据结构-最小生成树)

Minimal Ratio Tree Problem Description For a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation. Given a complete graph of n nodes with all nodes and edges weighted, your task is to find a

HDU 4965 Fast Matrix Calculation 【矩阵】

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4965 题目大意:给你一个N*K的矩阵A以及一个K*N的矩阵B (4 <= N <= 1000)以及 (2 <=K <= 6),然后接下来四步: 算一个新的矩阵C=A*B 算M=C^ (N*N) 对于M中的每个元素%6 将M中每个元素加起来,算出和. 也就是求出A*B * A*B * A*B * A*B * A*B *--* A*B   但是A*B形成的矩阵是N*N,而N大小有可能是10

hdu 5378 Leader in Tree Land(dp+逆元)

题目链接:hdu 5378 Leader in Tree Land 问题可以理解成N个节点的树,有K个ministers的概率,最后乘上N!.每个节点为ministers的概率即为1 / son(以该节点为根节点的子树包含的节点个数),同样不为ministers的概率为(son-1)/son.所以没有必要考虑树的结构,直接根句子节点的个数转移dp[i][j] dp[i][j] = dp[i-1][j-1] * 1 / son[u] dp[i][j] = dp[i-1][j] * (son[u]-

HDU 4896 Minimal Spanning Tree(矩阵快速幂)

题意: 给你一幅这样子生成的图,求最小生成树的边权和. 思路:对于i >= 6的点连回去的5条边,打表知907^53 mod 2333333 = 1,所以x的循环节长度为54,所以9个点为一个循环,接下来的9个点连回去的边都是一样的.预处理出5个点的所有连通状态,总共只有52种,然后对于新增加一个点和前面点的连边状态可以处理出所有状态的转移.然后转移矩阵可以处理出来了,快速幂一下就可以了,对于普通的矩阵乘法是sigma( a(i, k) * b(k, j) ) (1<=k<=N), 现在

hdu 4603 Color the Tree 2013多校1-4

这道题细节真的很多 首先可以想到a和b的最优策略一定是沿着a和b在树上的链走,走到某个点停止,然后再依次占领和这个点邻接的边 所以,解决这道题的步骤如下: 预处理阶段: step 1:取任意一个点为根节点,找出父子关系并且对这个树进行dp,求出从某个节点出发往下所包含的所有边的权值总和  复杂度O(n) step 2:从tree dp 的结果中计算对于某个节点,从某条边出发所包含的边的综合,并且对其从大到小进行排序 复杂度O(n*logn) step 3:dfs求出这颗树的欧拉回路,以及每个点的