首页 > ACM题库 > HDU-杭电 > HDU 3070-Counting spanning trees-动态规划-[解题报告]HOJ
2014
03-01

HDU 3070-Counting spanning trees-动态规划-[解题报告]HOJ

Counting spanning trees

问题描述 :

Everyone knows spanning trees, especially MST problem. But most of them are not familiar with degree constrained spanning tree.
a degree-constrained spanning tree is a spanning tree which the maximum vertex degree is limited to a certain constant d.
Given two integers n and d, your task is to count the number of degree constrained spanning trees of a (labeled) complete graph with n vertices.

输入:

Each line contains two integers n, d. 1<=n<=100, 1<=k<=100.

输出:

Each line contains two integers n, d. 1<=n<=100, 1<=k<=100.

样例输入:

3 1
3 2
4 2
10 3

样例输出:

0
3
12
3458313

首先有个现成结论,根据pseudo code,可以把n个点无度数限制的生成树的个数映射到n个数放到n-2个位置上的个数,即n^(n-2);但是当每个点的度数被限制为d时,即每个数最多能放在d个位置上,这时候就没有直接公式了。

先看下那个公式:n^(n-2)是从每个位置考虑过来,每个位置有n种可取,做n-2次这样的操作n^(n-2)。

换个角度思考:

  从每个数考虑过来,即是每个数最多能被d个位置使用。

  这时候就可以得出递推公式:

      dp[i][j]=(dp[i][j]+dp[i-1][j-k]*C(k,n-2-(j-k)));

dp[i][j]表示放完第i个数,用掉j个位置总共有多少种方法。

#include<iostream>
using namespace std;
#define MAXN 150
#define MOD 20090829
__int64 dp[MAXN][MAXN],c[MAXN][MAXN];
__int64 a[MAXN];
__int64 b[MAXN];
int gcd(int x,int y)
{
    if (y==0) return x;
    else return gcd(y,x%y);
}
__int64 C(int k,int n)
{
    int i,j;
    if (c[k][n]!=0) return c[k][n];
    __int64 temp,ans;
    for(i=n-k+1;i<=n;i++) a[i]=i;
    for(i=1;i<=k;i++) b[i]=i;
    for(i=1;i<=k;i++)
      for(j=n-k+1;j<=n;j++)
            {
               temp=gcd(b[i],a[j]);
               b[i]/=temp;
               a[j]/=temp;
            }
    
        ans=1;
        for(i=n-k+1;i<=n;i++)
            ans=ans*a[i]%MOD;
        c[k][n]=ans;
        return ans;
}
int min(int x,int y)
{
    if (x<y) return x;
    else return y;
}
int main()
{
    int n,d,i,j,k;
    __int64 ans;
    memset(c,0,sizeof(c));
    while(scanf("%d %d",&n,&d)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(i=1;i<=n;i++)
            for(j=0;j<=n-2;j++)
                for(k=0;k<=min(j,d-1);k++)
                {
                    dp[i][j]=(dp[i][j]+dp[i-1][j-k]*C(k,n-2-(j-k)))%MOD;
                }
        ans=dp[n][n-2];
        printf("%I64d/n",ans);
    }
}

参考:http://blog.csdn.net/SwordHoly/article/details/5924177


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  3. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count