题意:
有n个街口和m条街道, 你后边跟着警察,你需要进行大逃亡(又是大爱的抢银行啊),在每个街口你都有≥1个选择,
1)停留在原地5分钟。
2)如果这个街口可以到xi这个街口, 并且, 通过xi可以遍历完所有未走过的街口,那么就加入选择。
每个选择都是等概率的。
求警察抓住你所用时间的期望, 即你无路可走时的时间期望。
思路:
对于每个点, 先找出所有的选择, 假设有k个选择。
那么E[i] 表示在街口i时被抓的时间期望。
则, E[i] = 1 / k * sigma (E[u] + time[i][u]) + 1 / k * (E[i] + 5)。
化简得:E[i] = (sigma (E[u] + time[i][u]) + 5) / (k - 1)
用staues表示从i点出发, 到达状态staues所用的期望, 即所经历的点。
代码:
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-7
#define MAXN 110
#define MAXM 16
#define dd cout<<"debug"<<endl
#define p(x) printf("%d\n", x)
#define pd(x) printf("%.7lf\n", x)
#define k(x) printf("Case %d: ", ++x)
#define s(x) scanf("%d", &x)
#define sd(x) scanf("%lf", &x)
#define mes(x, d) memset(x, d, sizeof(x))
#define f(i, x) for(i = 0; i < x; i ++)
int n, m;
int w[MAXN][MAXN];
double E[MAXM][ << MAXM];
bool vis[MAXM][ << MAXM]; bool dfs(int staues, int root)
{
if(staues == ( << n) - )
{
E[root][staues] = ;
return true;
}
if(vis[root][staues]) return E[root][staues] > ;
vis[root][staues] = true;
E[root][staues] = ;
int cnt = , sttemp;
int i;
f(i, n)
if(!(staues & ( << i)) && w[root][i] != INF && dfs((staues | ( << i)), i))
{
sttemp = staues | ( << i);
cnt ++;
E[root][staues] += w[root][i] + E[i][sttemp];
}
if(!cnt)
{
E[root][staues] = ;
return false;
}
E[root][staues] /= cnt;
return true;
} int main()
{
int T;
int kcase = ;
s(T);
while(T --)
{
int u, v;
int ww;
s(n), s(m);
mes(w, 0x3f);
mes(vis, false);
int i;
f(i, m)
{
s(u), s(v), s(ww);
w[u][v] = w[v][u] = ww;
}
dfs(, );
k(kcase), pd(E[][]);
}
return ;
}