239
HDU 4305 無向連通圖的生成樹個數 矩陣行列式取模
題意：給出n個人和他們的坐標，閃電隨機劈到一個機器人，在他周圍的與他距離不超過r的機器人會被傳播，但是三點共線的情況隻能傳染最近的那個，傳染後的有多少種情況。
也就是無相連通圖的生成樹的個數。
對於一個無向連通圖來說，它可能有很多生成樹，那麼如何求得它的生成樹個數呢？
首先給出一個非常一般的計算方法 -- 矩陣行列式法
對於任何一個頂點數為n的無向連通圖，我們列出一個矩陣。
矩陣的規則是：
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。
這樣的一個矩陣Matrix就會很容易的用O(n^2)的複雜度建立。接下來如何求得這個無向連通圖的生成樹個數呢。
直接給出定理：
撤去任意一個節點的信息，求出剩下的(n-1)*(n-1)矩陣的行列式，此值即為這個無向連通圖的生成樹個數。複雜度為O(n^3)
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 305
int a[maxn][maxn],x[maxn],MOD;
int map[maxn][maxn];
int gauss(int r, int c)
{
bool flag=false;
int coe=1;
int i=0,t=0;
for(int j=0; j<c; ++j)
{
int index=i;
for(int k=i; k<r; ++k)
if(a[k][j]>0)
{
index=k;
break;
}
if(a[index][j])
{
if(index != i)
{
for(int k=j; k<c; ++k)
swap(a[i][k],a[index][k]);
flag = !flag;
}
for(int k=i+1; k<r; ++k)
if(a[k][j])
{
coe=(coe*a[i][j])%MOD;
++ t;
for(int l=c-1; l>=j; --l)
{
a[k][l]=(a[k][l]*a[i][j]-a[i][l]*a[k][j])%MOD;
if(a[k][l]<0)
a[k][l]+=MOD;
}
}
++i;
}
}
for(i=1; i<MOD; ++i)
if((coe*i)%MOD==1)
break;
int result=i;
for(i=0; i<r; ++i)
result=(result*a[i][i])%MOD;
if(flag)
result =MOD-result;
return result;
}
struct point
{
int x,y;
};
inline int dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline int Direction(point pi,point pj,point pk) //判斷向量PiPj在向量PiPk的順逆時針方向 +順-逆0共線
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
inline bool On_Segment(point pi,point pj,point pk)
{
if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y))
return 1;
return 0;
}
int main()
{
MOD=10007;
point data[maxn];
int n,r,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&r);
r*=r;
memset(a,0,sizeof(a));
memset(map,0,sizeof(map));
for(int i=0; i<n; i++)
scanf("%d%d",&data[i].x,&data[i].y);
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
if(dis(data[i],data[j])<=r)
map[i][j]=1,map[j][i]=1;
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
for(int k=0; k<n; k++)
if(j!=k&&i!=k&&Direction(data[i],data[j],data[k])==0&&On_Segment(data[i],data[j],data[k]))
map[i][j]=0,map[j][i]=0;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(map[i][j])
a[i][j]=-1;
for(int i=0; i<n; i++)
{
int num=0;
for(int j=0; j<n; j++)
if(map[i][j])
num++;
a[i][i]=num;
}
int ans=gauss(n-1,n-1);
if(ans==0)
puts("-1");
else
printf("%d\n",ans);
}
return 0;
}
最後更新：2017-04-03 18:52:05