HDU 4305 Lightning(Count spanning trees)

Description

求生成树有几种形状？

Analyze

跟普通生成树计数不同的是，例如一个三角形的图的生成树有三种形状，倘若把这个三角形压成一条线，那生成树就只有一种形状了。

解决办法是：若某两点看似可以连接时，判断一下，若两点连线中间还有点，则这两点不能连线。

Attention

关于取模，含有负数时((x % mod) + mod) % mod，不含有负数时x % mod,倘若有除法取模要用逆元，据说少量逆元可以类似递推出来？

void init()
{
    inv[1]=1;
    for(int i = 2;i < M;i++)
        inv[i] = (M - M / i) * inv[M % i] % M;
}

时间卡的紧：

本来用double的数据迫不得已改用了int

多个判断条件并列时，耗时少的判断放前面

if(A && B && C)
{
    //do something;
}

比如上述代码，A可能只是个普通bool型变量，B可能是一个长长的表达式，C可能是一个循环才能算得出值的bool变量

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define mod int(1e4 + 7)
const int N = 305;

int n, b[N][N], R, x[N], y[N];

double getDis(int u, int v)
{
    return sqrt( (x[u] - x[v])*(x[u] - x[v]) + (y[u] - y[v])*(y[u] - y[v]) );
}

bool sameLine(int a, int b, int c)
{
    bool line = (x[a] - x[b])*(y[b] - y[c]) == (y[a] - y[b])*(x[b]-x[c]);
    bool middle = (x[c] > x[a] && x[c] < x[b]) || (x[c] > x[b] && x[c] < x[a]) ;
    return line && middle;
}



int Gauss()
{
    int res = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            b[i][j] %= mod;
    for(int i = 2; i <= n; ++i)
    {
        for(int j = i + 1; j <= n; ++j)
        {
            while(b[j][i])///turn first not 0 element in row[j] into 0
            {
                int t = b[i][i] / b[j][i];
                for(int k = i; k <= n; ++k)
                    b[i][k] = (b[i][k] - b[j][k] * t) % mod;
                swap(b[i], b[j]);
                res = -res;
            }
        }
        if(b[i][i] == 0)
            return -1;
        res = (res * b[i][i]) % mod;
    }
    return (res + mod) % mod;
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d %d", &n, &R);
        memset(b, 0,sizeof(b));

        for(int i = 1; i <= n; ++i)
            scanf("%d %d", &x[i], &y[i]);
        for(int i = 1; i <= n; ++i)
            for(int j = i + 1; j <= n; ++j)
            {
                if(!(getDis(i, j) <= R))
                    continue;
                bool flag = 1;
                for(int k = 1; k <= n; ++k)
                    if(k != i && k != j && sameLine(i, j, k))
                    {
                        flag = 0;
                        break;
                    }
                if(flag)
                    b[i][i]++, b[j][j]++, b[i][j] = b[j][i] = -1;
            }
        cout << Gauss() << '\n';
    }
    return 0;
}