hdu5001(DP+概率)

題意:

給出一張圖;

n個點,m條邊,然後走d步;

問走d步不經過第i個點的概率(輸出n行,每個點算一次)

思路:

dp[i][j]代表走d步到達j點的概率;

我們可以知道dp[0][j] = 1.0 / n (還沒走,以每個點為起點的概率是一樣的);

然後我們還可以知道dp[i][j] = dp[i - 1][v[j][k]] / v[j].size(); 就是第i步到j,等於第i-1步到j的臨邊的概率並除以臨邊的數量的疊加;

在所有過程中我們要除掉我們所要求的點;

那麼dp[d][1] + dp[d][2] ......就是經過ｄ步到達所有點的概率加起來（全都不包括我要求的點），就得到所有不經過該點的概率了；

ＡＣ代碼：

#include
#include
#include
#include
using namespace std;

const int N = 55;
int n,m,d;
double dp[10005][N];
vector v[N];

void solve(int x) {
	for(int i = 1; i <= d; i++) {
		for(int j = 1; j <= n; j++) {
			if(j == x)
				continue;
			for(int k = 0; k < v[j].size(); k++) {
				if(v[j][k] != x)
					dp[i][j] += (dp[i - 1][v[j][k]])/v[j].size();
			}
		}
	}
	double ret = 0;
	for(int i = 1; i <= n; i++) {
		if(i != x)
			ret += dp[d][i];
	}
	printf("%.10lf\n",ret);
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		for(int i = 0; i <= n; i++) {
			v[i].clear();
		}
		scanf("%d%d%d",&n,&m,&d);
		int x,y;
		for(int i = 1; i <= m; i++){
			scanf("%d%d",&x,&y);
			v[x].push_back(y);
			v[y].push_back(x);
		}
		for(int i = 1; i <= n ;i++) {
			memset(dp, 0, sizeof(dp));
			for(int j = 0; j <= n; j++) {
				dp[0][j] = 1.0 / (double)n;
			}
			solve(i);
		}
	}
}