当前位置: 首页 > 工具软件 > lightning4j > 使用案例 >

【HDU 4305】Lightning

萧光华
2023-12-01

1.题目链接。题目大意:给定平面上n个点和一个距离r,任意两个点之间有边的条件是:两个点的欧几里得距离小于等于r并且这两个点之间的连线不再有其他的点。然后问有多少种方法使得所有的点都联通。

2.显然,这个图的每个生成树都是满足条件的,所以这个题其实就是在问(假设已经连边连好了),给定的这个图有多少棵生成树??关于生成树的计数问题,似乎有个Cayley定理,他说一个n个点的完全图有n^(n-2)棵生成树,其实这个定理的证明方法,可以采用无向图的Prufer序列的性质证明,也可以采用我们本题的Matrix-Tree定理。

3.Matrix-Tree定理告诉我们:一个图的生成树的数量和一个矩阵有关,这个矩阵就是该图的基尔霍夫矩阵,一个图的基尔霍夫矩阵等于这个图的度数矩阵-邻接矩阵。得到这个矩阵之后,生成树的数量就是这个矩阵任意n-1阶行列式的值。至于证明,就算了,因为有点复杂。

4。那么回到这个题,我们首先建图,建图其实还是很简单的,直接n^3建图,对于每两个点,枚举一下中间点,判断是不是有共线的存在,如果没有,那么就我们就没必要在构建度数矩阵和邻接矩阵,直接构建基尔霍夫矩阵就行(PS:防止有的童鞋看不懂代码,我解释一下怎么直接构建基尔霍夫矩阵,因为度数矩阵的定义是V[i][i]就是代表第i个点的度数,所以这个矩阵只有对角线上有值,其他的地方都是0,而邻接矩阵,只要是这个地方有边,就是1.可以看出无向图的邻接矩阵是一个对称矩阵,所以当用度数矩阵-邻接矩阵时,对于每对点(i,j),如果是存在边的,那么基尔霍夫矩阵对角线上mat[i][i],mat[j][j]要加一,而对应(i,j),(j,i)这里就是-1,因为我们保证i!=j.并且度数矩阵这里一定是0,所以减一就是-1)然后构造好矩阵之后,求一下行列式的值就行了,至于行列式的值怎么求,这个方法多种,不再深入探究。

#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
using namespace std;
const int M = 10007;//模数
const int N = 301;//点数
int mat[N][N];
//计算一个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 0;
		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;
}
double dis(point a, point b)
{
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n, r;
		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 (dis(p[i], p[j]) <= r)
				{
					int flag = 1;
					for (int k = 0; k < n; k++)
					{
						if (k != j && k != i && same(p[i], p[j], p[k]))
						{
							flag = 0;
						}
					}
					if (flag)
					{
						mat[i][j] = -1;
						mat[j][i] = -1;
						mat[i][i]++;
						mat[j][j]++;
					}
				}
			}
		}
		int ans = det(mat, n - 1);
		if (ans == 0)
		{
			cout << -1 <<endl;
		}
		else
		{
			cout << ans << endl;
		}
		
	}
}

 

 类似资料:

相关阅读

相关文章

相关问答