M_sea

UVa11600 Masud Rana
UVaLuogu分析不会做,自闭了 /kk首先把本来就能到达的城市缩成一个点。设 $dp_{i,S}$ 表示当前在...
扫描右侧二维码阅读全文
10
2019/08

UVa11600 Masud Rana

UVa

Luogu

分析

不会做,自闭了 /kk

首先把本来就能到达的城市缩成一个点。

设 $dp_{i,S}$ 表示当前在第 $i$ 个点,已经打通了 $S$ 中城市的期望天数。

设 $num$ 为 $S$ 中城市的数目,$cnt_i$ 为第 $i$ 个点的城市数目,可以写出转移

$$ dp_{i,S}=\frac{n-1}{n-num}+\sum_{j\notin S}dp_{j,S+\{j\}}\times\frac{cnt_j}{n-num} $$

然后 $S$ 很大,unordered_map 存即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30+10;

int n,m;
int G[N][N];

int tot,bl[N],sz[N];
inline void dfs(int u) {
    bl[u]=tot,++sz[tot];
    for (re int v=1;v<=n;++v)
        if (G[u][v]&&!bl[v]) dfs(v);
}

unordered_map<int,double> dp[N];
inline int sum(int S) {
    int res=0;
    for (re int i=1;i<=tot;++i)
        if (S&(1<<(i-1))) res+=sz[i];
    return res;
}
inline double dfs(int u,int S) {
    if (dp[u].count(S)) return dp[u][S];
    int num=sum(S);
    if (num==n) return 0;
    double res=1.0*(n-1)/(n-num);
    for (re int i=1;i<=tot;++i) {
        if (S&(1<<(i-1))) continue;
        res+=dfs(i,S|(1<<(i-1)))*sz[i]/(n-num);
    }
    return dp[u][S]=res;
}

int main() {
    int T=read();
    for (re int _=1;_<=T;++_) {
        n=read(),m=read();
        for (re int i=1;i<=m;++i) {
            int u=read(),v=read();
            G[u][v]=G[v][u]=1;
        }
        for (re int i=1;i<=n;++i)
            if (!bl[i]) ++tot,dfs(i);
        double ans=dfs(1,1);
        printf("Case %d: %.6lf\n",_,ans);
        memset(G,0,sizeof(G));
        memset(bl,0,sizeof(bl)),memset(sz,0,sizeof(sz)),tot=0;
        for (re int i=1;i<=n;++i) dp[i].clear();
    }
    return 0;
}
最后修改:2019 年 08 月 10 日 10 : 10 PM

2 条评论

  1. Itst

    这能过???

    1 30 0不是随便卡???

    1. M_sea
      @Itst

      我也不知道为啥能过啊 /wq

发表评论