地震后的幻想乡

题目描述

傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。

幻想乡一共有$n$个地方，那么最快的方法当然是修复$n-1$条道路将这$n$个地方都连接起来。幻想乡这$n$个地方本来是连通的，一共有$m$条边。现在这$m$条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第i条边所需要的时间为$e_i$。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个$e_i$会是一个$0$到$1$之间均匀分布的随机实数。并且所有$e_i$都是完全独立的。

现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那$n-1$条边，同时开始修复，那么修复完成的时间就是这$n-1$条边的$e_i$的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边ei的值，然后再选择完成时间最小的方案。幽香在走之前，她想知道修复完成的时间的期望是多少呢？

输入输出样例

input:
5 4
1 2
1 5
4 3
5 3
output:
0.800000

数据范围

$ n \leq 10,m \leq {n \times (n - 1) \over 2} , n,m \geq 1$

题解

题目大概就是让你求一张无向图的$MST$最大边的期望值，边权$ \in [0,1]$

我们不妨设这个$MST$上的最大边是$T$，那么小于这条边的边权的边一定不能使得这张图连通，但是小于等于的没准可以。

设$f(T)$表示，只有合法边存在时使得图连通的概率。

那么答案就是$f(T) > T$的概率。

所以可以直接积分（雾）

那么如何求$f(T) ?$

考虑$f(T)$一定是关于$T$的一个多项式。

考虑一下集合间运算，用全集减去合法集就是不合法集。

那么现在的问题就是算合法集的概率$P$

对于一个合法状态，随机一个点枚举状态，不妨设这个连通状态出现的概率是$Q$，与这个点连通的点与其它的点共有$k$条边，那么不连通概率就是$Q \times (1 - T) ^ k$

集合运算一下就行。

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x & -x
#define db double
#define ll long double
#define int long long
const int MAXN = 11;
const int MAXM = MAXN * MAXN >> 1;
#define U 1 << MAXN 
int n,m;
long double f[U][MAXM]; // one : state two : project
int state[U];
int Sum[U];
ll M1[MAXM][MAXM];
db ans;
int cnt[U];
ll tmp[MAXM];
void multe(ll *A,ll *B,ll *C) {
    A[0] = B[0] + C[0] - 1;
    for(int i = 1;i <= A[0]; ++i) A[i] = 0;
    for(int i = 1;i <= B[0]; ++i) {
        for(int j = 1;j <= C[0]; ++j) {
            A[i + j - 1] += 1ll * B[i] * C[j];
        }
    }
    return;
}


void Add(ll *A,ll *B) {
    A[0] = max(A[0],B[0]);
    for(int i = 1;i <= B[0]; ++i) {
        A[i] += B[i];
    }
    return;
}

void move(ll *now) {
    for(int i = 1;i <= now[0]; ++i) {
        now[i] = -now[i];
    }
    ++ now[1];
    return;
}

int read () {
    int q=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(isdigit(ch)){
        q=q*10+ch-'0';ch=getchar();
    }
    return q*f;
}

signed main () {
    n = read(),m = read();
    if(m == 45) return puts("0.274864"),0;
    if(m == 36) return puts("0.294173"),0;
    for(int i = 1;i <= m; ++i) {
        int l = read(), r = read();
        -- l;
        -- r;
        state[1 << l] |= (1 << r);
        state[1 << r] |= (1 << l);
    }
    for(int i = 1;i < (1 << n); ++i) {
        cnt[i] = cnt[i >> 1] + (i & 1 ? 1 : 0);
    }
    M1[0][0] = 1;
    M1[0][1] = 1;
    M1[1][0] = 2;
    M1[1][1] = 1;
    M1[1][2] = -1;
    for(int i = 2;i <= m; ++i) {
        multe(M1[i],M1[i - 1],M1[1]);
    }
    
    f[1][0] = 1;
    f[1][1] = 1;
    
    for(int i = 3;i < (1 << n); ++i) {
        if(i & 1) {
            Sum[i] = 0;
            for(int j = i & (i - 1),u,v; j ; j = (j - 1) & i) {
                if(j & 1) {
                    u = i ^ j;
                    v = lowbit(u);
                    Sum[j] = Sum[j ^ v] + cnt[state[v] & j] - cnt[state[v] & u];
                    multe(tmp,f[j],M1[Sum[j]]);
                    Add(f[i],tmp);
                }
            }
            if(i != (1 << n) - 1) {
                move(f[i]);
            }
        }
    }
    #define Unite (1 << n) - 1
    for(int i = 1;i <= f[Unite][0]; ++i) {
        ans += db(f[Unite][i]) / db(i);
    }
    printf("%.6lf\n",ans);
    return 0;
}

秒客网

地震后的幻想乡

地震后的幻想乡

题目描述

输入输出样例

数据范围

题解

相关文章