UVA 11600 Masud Rana（期望+状压DP）

深藏阁楼爱情的钟 2021-11-17 00:40 338阅读 0赞

## 题意：n个城市，城市间两两有一条道路，m条道路是没有怪物的，每天随机选一个城市（除了本身），走过去，消灭途中的怪物，如果消灭完后，所有城市都可以不通过有怪物的道路到达就结束，问平均需要的天数。 ##

## 分析：图+期望+状压好题。求期望，逆推法。我们可以将互相间没有妖怪的城市看成一个点，因为他们对答案没有贡献。dp\[u\]\[s\]表示当前在u这点，已经可以互相到达的城市集合为s，令已经完成的城市数为have，则还没完成的为n - have。那么要选中一个未完成的城市的概率为(n - have) / (n  - 1)。也就是平均需要(n - 1) / (n - have)次才能走到未完成的城市，然后在加上s|(1<<i)之后状态需要的平均时间\*概率，概率为p\[i\] \* (n - have)。所以状态转移方程为dp\[u\]\[s\] = (n - 1) / ( n - have) + sum\{dp\[u\]\[s|(1<<i)\] \* （p\[i\] \* (n - have))\}。参考[https://blog.csdn.net/accelerator\_/article/details/20771697][https_blog.csdn.net_accelerator_article_details_20771697]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int N = 35;
    int t, n, m, p[N], pn, vis[N];
    vector<int> g[N];
    map<int, double> dp[N];
    
    int bitcount(int x) {
    	if (x == 0) return 0;
    	else return bitcount(x/2) + (x&1);
    }
    
    int dfs(int u) {
    	vis[u] = 1;
    	int ans = 1;
    	for (int i = 0; i < g[u].size(); i++) {
    		int v = g[u][i];
    		if (vis[v]) continue;
    		ans += dfs(v);
    	}
    	return ans;
    }
    
    double DP(int u, int s) {
    	if (dp[u].count(s)) return dp[u][s];
    	int have = 0, i;
    	for (i = 0; i < pn; i++) {
    		if (s&(1<<i))
    			have += p[i];
    	}
    	if (have == n) return dp[u][s] = 0;
    	dp[u][s] = (n - 1) * 1.0 / (n - have);
    	for (i = 0; i < pn; i++) {
    		if (s&(1<<i)) continue;
    		dp[u][s] += DP(i, s|(1<<i)) * p[i] / (n - have);
    	}
    	return dp[u][s];
    }
    
    int main() {
    	int cas = 0;
    	scanf("%d", &t);
    	while (t--) {
    		pn = 0;
    		memset(vis, 0, sizeof(vis));
    		memset(g, 0, sizeof(g));
    		scanf("%d%d", &n, &m);
    		int u, v;
    		while (m--) {
    			scanf("%d%d", &u, &v);
    			g[u].push_back(v);
    			g[v].push_back(u);
    		}
    		for (int i = 1; i <= n; i++) {
    			if (vis[i]) continue;
    			dp[pn].clear();
    			p[pn++] = dfs(i);
    		}
    		printf("Case %d: %.6lf\n", ++cas, DP(0, 1));
    	}
    	return 0;
    }

[https_blog.csdn.net_accelerator_article_details_20771697]: https://blog.csdn.net/accelerator_/article/details/20771697