LightOj_1287 Where to Run

题目链接

题意：

　　有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 ;

 }

巴特西

LightOj_1287 Where to Run

最新文章

热门文章