hihoCode 1075 : 开锁魔法III

时间限制:6000ms

单点时限:1000ms

内存限制:256MB

描述

一日，崔克茜来到小马镇表演魔法。

其中有一个节目是开锁咒：舞台上有 n 个盒子，每个盒子中有一把钥匙，对于每个盒子而言有且仅有一把钥匙能打开它。初始时，崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后所有盒子都被打开的概率，你能帮助她回答这个问题吗？

输入

第一行一个整数 T (T ≤ 100)表示数据组数。对于每组数据，第一行有两个整数 n 和 k (1 ≤ n ≤ 300, 0 ≤ k ≤ n)。第二行有 n 个整数 a_i，表示第 i 个盒子中，装有可以打开第 a_i 个盒子的钥匙。

输出

对于每组询问，输出一行表示对应的答案。要求相对误差不超过四位小数。

样例输入

样例输出

0.000000000

0.600000000

0.900000000

1.000000000

题解：
　　这个题目十分巧妙，首先，我们想利用题目中已经告诉我们们的一个性质，对于每个盒子而言有且仅有一把钥匙能打开它，所以，如果我们把一个盒子看成一个点，那么你打开一个盒子，就可以前往盒子里下标的那个点，那么又因为图上的那个性质，相当于保证了每个点的如果只能为一，且出度也为一，所以整个图就会由若干环环组成。
　　知道这个，我们想把每个点都跑到，那么显然每个环都至少存在一个点就可以了。那么考虑ｄｐ出所有可行的方案数，dp[i][j]表示处理到ｉ这个环，用了ｊ次选点机会的方案数，那么dp[i][j]=dp[i][j-use]*c(size[i],use)。其中use表示你用于ｉ这个环上选的点数，size[i]表示ｉ这个环的点数。dp[0][0]=1.
　　最后用dp[num][k]除以总方案数就可以了。

代码：

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

#define MAXN 320

using namespace std;

double c[MAXN][MAXN];

int size[MAXN],b[MAXN],g[MAXN];

double dp[MAXN][MAXN];

int n,k;

void pre(){

    c[][]=;

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

        for(int j=;j<=;j++){

            if(!j) c[i][j]=;

            else c[i][j]=c[i-][j-]+c[i-][j];

        }

}

int main()

{

    int t;cin>>t;

    pre();

    while(t--){

        scanf("%d%d",&n,&k);

        memset(g,,sizeof(g));

        for(int i=;i<=n;i++) scanf("%d",&g[i]);

        int num=;

        memset(b,,sizeof(b));

        memset(size,,sizeof(size));

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

            if(b[i]) continue;

            num++;int now=i;

            while(!b[now]){

                b[now]=;

                size[num]++;

                now=g[now];

            }

        }

        if(k<num){

            printf("%0.9f\n",);

            continue;

        }

        memset(dp,,sizeof(dp));

        dp[][]=;

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

            for(int j=;j<k;j++){

                if(!dp[i][j]) continue;

                for(int use=;use<=size[i+]&&j+use<=k;use++){

                    dp[i+][j+use]+=dp[i][j]*c[size[i+]][use];

                }

        }

        printf("%0.9f\n",dp[num][k]/c[n][k]);

    }

    return ;

}

巴特西

hihoCode 1075 : 开锁魔法III

描述

输入

输出

最新文章

热门文章