uva11600 状压期望dp

时间：2022-03-21 15:19:06

一般的期望dp是， dp[i] = dp[j] * p[j] + 1; 即走到下一步需要1的时间，然后加上 下一步走到目标的期望*这一步走到下一步的概率

这一题，我们将联通分块缩为一个点，因为联通块都是安全的

dp[u][s] 为当前在u，走过的联通块为s的期望天数

那么走到剩下没有走过的连通块的概率是   (n-have)/(n-1),  那么平均需要的时间是  (n-1)/(n-have),

走到下一个没有走过的连通块的概率为cnt[i] / (n-have)

所以dp[u][s] = (n-1)/(n-have) + dp[i][s|1<<i] * cnt[i]/(n-have)

 #pragma warning(disable:4996)

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <stdio.h>

 #include <string.h>

 #include <time.h>

 #include <math.h>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <bitset>

 #include <algorithm>

 #include <iostream>

 #include <string>

 #include <functional>

 const int INF =  << ;

 typedef __int64 LL;

 /*

 */

 const int N =  + ;

 std::vector<int> g[N];

 std::map<int, double> dp[N];

 int cnt[N];

 int p, n;

 bool vis[N];

 int dfs(int u)

 {

     vis[u] = true;

     int ret = ;

     for (int i = ;i < g[u].size();++i)

     {

         int v = g[u][i];

         if (vis[v]) continue;

         ret += dfs(v);

     }

     return ret;

 }

 double DP(int u, int s)

 {

     int have = ;

     if (dp[u].count(s)) return dp[u][s];

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

         if (s&( << i))

             have += cnt[i];

     if (have == n) return ;//dp[][n] 的期望是0

     dp[u][s] = (n - )*1.0 / (n - have);

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

     {

         if (s&( << i)) continue;

         dp[u][s] += DP(i, s|( << i)) * cnt[i] / (n - have);

     }

     return dp[u][s];

 }

 int main()

 {

     int t, m;

     scanf("%d", &t);

     for (int k = ;k <= t;++k)

     {

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

         p = ;

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

         {

             g[i].clear();

             vis[i] = ;

         }

         int u, v;

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

         {

             scanf("%d%d", &u, &v);

             g[u].push_back(v);

             g[v].push_back(u);

         }

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

             if (!vis[i])

             {

                 dp[p].clear();

                 cnt[p++] = dfs(i);

             }

         printf("Case %d: %.6lf\n",k, DP(, ));

     }

     return ;

 }

相关文章