程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 11600 - Masud Rana(記憶化搜索）

uva 11600 - Masud Rana(記憶化搜索）

編輯：C++入門知識

題目鏈接：uva 11600 - Masud Rana

題目大意：給出n和m，表示說有n座城市，每兩座城市間有一條路，每條路上都有怪物，現在有m條路上沒有怪物，給出沒有怪物的路。現在任選一座城市移過去，清除路上的怪物，當所有城市可以直接連接時終止，問說需要移動次數的期望。

解題思路：首先將已經聯通的城市算成是一個聯通集，這樣的話，就有k個聯通集，k小於三十，所以可以用二進制數來表示狀態，所以有d[u][s]表示說從u這個聯通即開始，已經聯通的狀態為s的情況下，還需要多少次的期望。轉移方程：link為已經聯通了的城市的數量，那麼n個城市，選中未聯通的可能性為(n-link)/(n-1),所以就是說有平均需要（n-1)/(n-link)次會選中為聯通的城市進行移動，d[u][s] =（n-1)/(n-link) + 剩下的聯通集的期望。

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N = 35;

int n, m, k, v[N], c[N];
vector g[N];
map d[N];

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

void init () {
	scanf("%d%d", &n, &m);

	int a, b;
	memset(v, 0, sizeof(v));
	for (int i = 1; i <= n; i++) g[i].clear();

	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}

	k = 0;
	for (int i = 1; i <= n; i++) if (!v[i]) {
		d[k].clear();
		c[k] = dfs(i);
		k++;
	}
}

double solve (int u, int s) {
	if (d[u].count(s)) return d[u][s];

	int link = 0;
	for (int i = 0; i < k; i++) if (s&(1<

C++入門知識

利用ascii碼加密字符串，ascii加密字符串

利用ascii碼加密字符串，ascii加密字符串算法：用原來

C++編程新思維中的技巧，編程新思維技巧

C++編程新思維中的技巧，編程新思維技巧 1.編譯

Sicily 1068歡迎提出優化方案

N <tex2html_ver

擴充C0文法編譯器開發筆記（一）符號表，c0文法

擴充C0文法編譯器開發筆記（一）符號表，c0文法零、簡介　

C++11 thread::joinable(5)

C++11 thread::joinable(5) &n

[hdu-2044] 一只小蜜蜂

一只小蜜蜂... Time Limit: 200