2012-C08-team5-problem-F

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <algorithm>
using namespace std;

int p,cnt[1<<14],x[100],y[100];
double dp[1<<14],rate[101]={1};

int main(){
    int n,m;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0;i<m;i++) rate[i+1]=rate[i]*p*0.01;
    for(int i=0;i<m;i++){
        scanf("%d%d",x+i,y+i);
        x[i]--,y[i]--;
    }
    int mask=(1<<n)-1;
    for(int s=0;s<=mask;s++) for(int i=0;i<m;i++)
        if((1<<x[i]&s) && (1<<y[i]&s)) cnt[s]++;
    for(int s=0;s<=mask;s++){
        dp[s]=1;
        for(int r=(s-1)&s;r>(s^r);r=(r-1)&s)
            dp[s]-=dp[r]*rate[cnt[s]-cnt[r]-cnt[s^r]];
    }
    printf("%.12f\n",dp[mask]);
}
}}}

#include <cstdio>
#include <algorithm>
using namespace std;
int p,cnt[1<<14],x[100],y[100];
double dp[1<<14],rate[101]={1};
int main(){
    int n,m;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0;i<m;i++) rate[i+1]=rate[i]*p*0.01;
    for(int i=0;i<m;i++){
        scanf("%d%d",x+i,y+i);
        x[i]--,y[i]--;
    }
    int mask=(1<<n)-1;
    for(int s=0;s<=mask;s++) for(int i=0;i<m;i++)
        if((1<<x[i]&s) && (1<<y[i]&s)) cnt[s]++;
    for(int s=0;s<=mask;s++){
        dp[s]=1;
        for(int r=(s-1)&s;r>(s^r);r=(r-1)&s)
            dp[s]-=dp[r]*rate[cnt[s]-cnt[r]-cnt[s^r]];
    }
    printf("%.12f\n",dp[mask]);
}