【生成树计数】HDU 4305 Lightning

KIDx的解题报告

 

题意：给出n个点，给出R，两点距离不大于R而且两点之间没其他点阻碍，就可以建一条边，问可以形成多少棵生成树，如果没有，输出-1，否则，输出（生成树个数 mod 10007）

 

典型的生成树计数：

①求出邻接矩阵G

②求出度数矩阵D

③D-G得出Kirchhoff矩阵

④求Kirchhoff矩阵任意n-1阶子矩阵的行列式

一些概念不懂的话还是要看看周冬的《生成树的计数及其应用》http://wenku.baidu.com/view/782ab9eb19e8b8f67c1cb9a9.html

 

当然取余方面要用到逆元的知识：

乘法逆元：

x*y ≡ 1mod (mod)，则称 x 是 y 对于mod的乘法逆元

分数取模就要用到了，如求(a/b) % mod = ?

那就要先解决b^-1 % mod = ?

就等价于b的逆元x%mod了，求出x即可变为求a*x % mod = ?

令y = b，x*y ≡ 1mod (mod) → x*y + k*mod == 1

用扩展欧几里德即可算出y的逆元x

 

#include <iostream>
using namespace std;
#define M 305

struct point{
	int x, y;
}p[M];

int C[M][M], G[M][M];
int mod = 10007;

int dis (point a, point b)
{
	return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

void Egcd (int a, int b, int &x, int &y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return ;
	}
	Egcd (b, a%b, x, y);
	int tp = x;
	x = y;
	y = tp - a/b*y;
}

int det (int n)    //计算n阶行列式
{
	int i, j, k, ans = 1, x, y, flg = 1;
	for (i = 0; i < n; i++)
	{
		if (C[i][i] == 0)
		{
			for (j = i+1; j < n; j++)
				if (C[j][i])
					break;
			if (j == n) return -1;
			flg = !flg;
			for (k = i; k < n; k++)
				swap (C[i][k], C[j][k]);
		}
		ans = ans * C[i][i] % mod;
		Egcd (C[i][i], mod, x, y);
		x = (x%mod + mod) % mod;			//注意保证取余结果为最小非负数
		for (k = i+1; k < n; k++)
			C[i][k] = C[i][k] * x % mod;
		for (j = i+1; j < n; j++)
			if (C[j][i] != 0) for (k = i+1; k < n; k++)
				C[j][k] = ((C[j][k] - C[i][k]*C[j][i])%mod + mod) % mod;
				//注意保证取余结果为最小非负数
	}
	if (flg) return ans;
	return mod-ans;
}

int main ()
{
	int i, j, k, t, n, r;
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d%d", &n, &r);
		for (i = 0; i < n; i++)
			scanf ("%d%d", &p[i].x, &p[i].y);
		memset (G, 0, sizeof(G));
		for (i = 0; i < n; i++)    //建图
		{
			for (j = i + 1; j < n; j++)
			{
				int tp = dis (p[i], p[j]);
				if (tp > r*r) continue;
				for (k = 0; k < n; k++)
				{
					if (k == i || k == j) continue;
					if ((p[i].x-p[k].x)*(p[j].y-p[k].y) ==
						(p[j].x-p[k].x)*(p[i].y-p[k].y) &&
						dis (p[i], p[k]) < tp && dis (p[j], p[k]) < tp)
						break;
				}
				if (k == n) G[i][j] = G[j][i] = 1;
			}
		}
		memset (C, 0, sizeof(C));
		for (i = 0; i < n; i++)
			for (j = i + 1; j < n; j++)
				if (G[i][j])
					++C[i][i], ++C[j][j];
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
			{
				C[i][j] -= G[i][j];
				C[i][j] = (C[i][j]%mod + mod) % mod;
				//注意保证取余结果为最小非负数
			}
		printf ("%d\n", det(n-1));
	}
	return 0;
}