LightOJ1287---Where to Run (概率dp) - c++编程基础

TOP

LightOJ1287---Where to Run (概率dp)(二)

2015-11-21 01:01:52 来源: 作者: 【大中小】浏览:4次

完图的期望时间
至于那个EJ点个数判断,可以事先dfs下来然后保存好,注意也要记忆化搜索

    /*************************************************************************
        > File Name: K.cpp
        > Author: ALex
        > Mail: zchao1995@gmail.com
        > Created Time: 2015年05月18日 星期一 18时29分15秒
     ************************************************************************/

    #include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; vector 
                  
                    roads[20]; int n; double dp[16][(1 << 15) + 10]; int ok[16][(1 << 15) + 10]; double DP(int u, int sta) { double &res = dp[u][sta]; if (res != -1.0) { return res; } int cnt = 0; int size = roads[u].size(); for (int i = 0; i < size; ++i) { int v = roads[u][i].first; if (sta & (1 << v)) { continue; } if (ok[v][sta | (1 << u)] == 1) { ++cnt; } } if (!cnt) { return res = 0; } res = 0; double p = 1.0 / (1 + cnt); for (int i = 0; i < size; ++i) { int v = roads[u][i].first; if (sta & (1 << v)) { continue; } if (!ok[v][sta | (1 << u)]) { continue; } int w = roads[u][i].second; res += p * w + p * DP(v, sta | (1 << u)); } res += 5.0 * p; res /= (1 - p); return res; } void dfs(int u, int sta) { if ((sta | (1 << u)) == (1 << n) - 1) { ok[u][sta] = 1; dp[u][sta] = 0; return; } ok[u][sta] = 0; int size = roads[u].size(); for (int i = 0; i < size; ++i) { int v = roads[u][i].first; if (!(sta & (1 << v))) { if (ok[v][sta | (1 << u)] == -1) { dfs(v, sta | (1 << u)); } ok[u][sta] = (ok[u][sta] || ok[v][sta | (1 << u)]); } } } int main() { int t, icase = 1; scanf("%d", &t); while (t--) { int m; scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { roads[i].clear(); } int u, v, w; for (int i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &w); roads[u].push_back(make_pair(v, w)); roads[v].push_back(make_pair(u, w)); } for (int i = 0; i < (1 << n); ++i) { for (int j = 0; j < n; ++j) { dp[j][i] = -1.0; ok[j][i] = -1; } } dfs(0, 0); printf("Case %d: %.12f\n", icase++, DP(0, 0)); } return 0; }

首页上一页 1 2 下一页尾页 2/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj2001 Shortest Prefixes	下一篇：poj2838 Graph Connectivity

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: