HDU 4305 Lightning （生成树的计数+矩阵树定理+逆元） - c++编程基础

TOP

HDU 4305 Lightning （生成树的计数+矩阵树定理+逆元）(一)

2014-11-23 19:09:17 来源: 作者: 【大中小】浏览:10次

Tags：HDU 4305 Lightning 生成计数矩阵定理 +逆元

题意：给你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    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
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<
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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(

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj3227	下一篇：poj 2289 (最大流+二分)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: