UVA 11600 Masud Rana —— 状压、概率 DP

传送门

题目大意:

Masud Rana 是孟加拉国反情报组织的一名间谍。他接到了一个任务。孟加拉国有 $n$ 个城市,每个城市与其他所有城市都有一条双向道路相连,所以孟加拉国一共有 $\frac{n \cdot (n - 1)}{2}$ 条道路。有一些道路被邪恶力量控制着。我们称一个城市 $a$ 到城市 $b$ 是安全可达的当且仅当有一条从 $a$ 到 $b$ 的路径没有被邪恶力量控制。已知当前在孟加拉国有 $m$ 条道路是安全的。 Masua Rana 的任务是消灭邪恶力量,使孟加拉国的任意两个城市安全可达。

Masud Rana 的选择了这样的策略:每天早上他随机选择一个除他现所在城市之外的一个城市,并通过直接相连的道路访问该城市。他会铲除他将要通过的道路上的邪恶力量。他会在该城市待一个晚上。第二天早上他会检查他的任务是否完成,若完成,则结束,若没有,重复以上步骤。

求 Masua Rana 完成任务的期望天数。

输入格式:

第一行一个整数 $T$ ,代表测试数据组数。

对于每组测试数据,第一行两个整数 $n\ (1 \leq n \leq 30)$ 和 $m\ (1 \leq m \leq \frac{n \cdot (n - 1)}{2})$ ,分别代表孟加拉国的城市数量与安全道路的数量。
接下来 $m$ 行,每行两个整数 $a, b$ ,代表 $a$ 到 $b$ 有一条安全的双向道路相连。

输出格式:

对于每组测试数据,输出一行一个浮点数,代表 Masud Rana 完成任务的期望天数。格式与样例一致。

精度误差在 $1E-6$ 以内。

测试样例:

Input
2
3 1
2 3
4 1
2 3
Output
Case 1: 1.0
Case 2: 3.5

分析:

这道题数据范围很小, $n$ 最大才 $30$ ,所以我们想到了状压。

首先我们知道,因为最开始就有道路是安全的,所以只有当每次选择一条邪恶道路,才会离任务完成更进一步。意思就是说,当 Masud Rana 从一个连通块到另一个连通块时,离完成任务更进一步。

所以第一步,我们求出所有的连通块,同时对连通块编号,并求出每个连通块内点的个存在 $cnt[]$ 数组里。我们需要状压的东西就是连通块。在二进制里,我们把已访问过的连通块置为 $1$ ,没有访问的置为 $0$ 。

接下来我们考虑 DP 状态:我们定义 dp[u][S] 代表目前在第 $i$ 个连通块、访问的连通块的状态集合为 $S$ 时,还需要多少天就可以完成任务。 注意这里最坏情况可能达到 $2^{30}$ ,开数组的话是开不下的,所以我们考虑用时间换空间,用 map<int, double> dp[35] 来存。

接下来我们考虑转移:

假设在当前集合 $S$ 中,已经访问的连通块中所有的节点数的和 为 $tot$ ,那么就还剩 $n - tot$ 个节点是没有访问的。下一步可以到达的节点是 $n - 1$ 个(他不能从当前节点走到当前节点),所以我们平均每 $\frac{n - 1}{n - tot}$ 步可以走到一个没有访问过的节点。假设当前节点为 $u$ ,那么 dp[u][S] 的初始值就为 $\frac{n - 1}{n - tot}$ 。

接下来,我们假设他下一个要访问的连通块是第 $i$ 个连通块 ,$i$ 没有在集合 $S$ 内,那么他有 $\frac{cnt_i}{n-tot}$ 的概率刚好到达第 $i$ 个连通块,我们用这个概率乘上 dp[i][S | (1 << i)] 的值,把它加到 dp[u][S] 里。

所有状态转移方程就是:

记忆化搜索写。

最后,如果写完,没有查出任何问题,交上去却是 TLE ,请把你的链式前向星换成 vector

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;

template<class _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && (_t < '0' || _t > '9'));
  if (_t == '-')  _t = getchar(), _flag = 1;
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = _x * 10 + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;

const int MAX_N = 32;
map<int, double> dp[MAX_N];
int n, m;
vector<int> G[MAX_N];
int k = 0, vis[MAX_N], cnt[MAX_N];

int dfs(int now) {
  vis[now] = 1;
  int ans = 1;
  for (int i = 0; i < G[now].size(); ++i) {
    int v = G[now][i];
    if (vis[v]) continue;
    ans += dfs(v);
  }
  return ans;
}

double DP(int now, int S) {
  if (dp[now].count(S)) return dp[now][S];
  int tot = 0;
  for (int i = 0; i < k; ++i) {
    if (S & (1 << i)) tot += cnt[i];
  }
  if (tot == n) return dp[now][S] = 0;
  dp[now][S] = (n - 1) * 1.0 / (n - tot);
  for (int i = 0; i < k; ++i) {
    if (!(S & (1 << i))) {
      dp[now][S] += 1.0 * cnt[i] / (n - tot) * DP(i, S | (1 << i));
    }
  }
  return dp[now][S];
}

void init() {
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= n; ++i)  G[i].clear();
  k = 0;
}

int main() {
  int T;
  read(T);
  int kase = 0;
  while (T--) {
    read(n), read(m);
    init();
    for (int i = 1; i <= m; ++i) {
      int a, b;
      read(a), read(b);
      G[a].push_back(b);
      G[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) {
      if (vis[i]) continue;
      dp[k].clear();
      cnt[k] = dfs(i);
      ++k;
    }
    double ans = DP(0, 1);
    printf("Case %d: %.6f\n", ++kase, ans);
  }
  return 0;
}