BZOJ 1005 prufer序列

给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Prufer数列是无根树的一种数列。

在组合数学中，Prufer数列由有一个对于顶点标过号的树转化来的数列，点数为n的树转化来的Prufer数列长度为n-2。

树转Prufer:

找到编号最小的度数为11的点
删除该节点并在序列中添加与该节点相连的节点的编号
重复1,21,2操作，直到整棵树只剩下两个节点

　　Prufer转树:

每次取出prufer序列中最前面的元素uu
在点集中找到编号最小的没有在prufer序列中出现的元素vv
给u,vu,v连边然后分别删除
最后在点集中剩下两个节点，给它们连边

性质:

#include <bits/stdc++.h>

using namespace std;

int d[];

struct bigint

{

    int a[], len;

    bigint()

    {

        memset(a, , ), len = ;

    }

    bigint operator* (const int &rhs) const

    {

        bigint ans;

        ans.len = len + ;

        for(int i = ; i <= len; ++i)

            ans.a[i] += a[i] * rhs;

        for(int i = ; i < ans.len; ++i)

            if(ans.a[i] > )

            {

                ans.a[i + ] += ans.a[i] / ;

                ans.a[i] %= ;

            }

        while(!ans.a[--ans.len]);

        return ans;

    }

    bigint operator/ (const int &rhs) const

    {

        bigint ans;

        ans = *this, ++ans.len;

        for(int i = ans.len; i; --i)

        {

            ans.a[i - ] += ans.a[i] % rhs * ;

            ans.a[i] /= rhs;

        }

        while(!ans.a[--ans.len]);

        return ans;

    }

};

int main()

{

    int n, sum = , cnt = ;

    bigint ans;

    scanf("%d", &n);

    for(int i = ; i <= n; ++i)

    {

        scanf("%d", d + i);

        if(!d[i])

        {

            puts("");

            return ;

        }

        if(~d[i]) ++cnt, sum += d[i] - ;

    }

    if(sum >  * n - )

    {

        puts("");

        return ;

    }

    ans.a[] = ;

    for(int i = n -  - sum; i < n - ; ++i)

        ans = ans * i;

    for(int i = ; i <= n -  - sum; ++i)

        ans = ans * (n - cnt);

    for(int i = ; i <= n; ++i)

        for(int j = ; j <= d[i] - ; ++j)

            ans = ans / j;

    for(int i = ans.len; i; --i)

        printf("%d", ans.a[i]);

    puts("");

    return ;

}

巴特西

BZOJ 1005 prufer序列

最新文章

热门文章