设为首页 加入收藏

TOP

LightOJ1287---Where to Run (概率dp)(二)
2015-11-21 01:01:52 来源: 作者: 【 】 浏览:4
Tags:LightOJ1287---Where Run 概率
完图的期望时间
至于那个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

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: