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;
}
分享到:
相关推荐
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
NULL 博文链接:https://128kj.iteye.com/blog/1734821
hdu 1166线段树代码
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
hdu 1166线段树
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码