当前位置：首页 > news >正文

hdu 4035 可能性DP 成都网络游戏

news 来源：原创 2024/5/2 12:05:28

http://acm.hdu.edu.cn/showproblem.php?pid=4035

获得：

1、首先推断是不是树。事实上，所有的感觉身影，既看边数==算-1是不成立

2、有时候，我告诉孩子来区分树仍然是必要的，就是，只是是在dfs的时候，传參数的时候多加个表示父节点的參数而已

3、一定注意，概率DP对精度真的要求非常高開始的时候写1e-8,WA了好几发，改了1e-10 AC

4、注意分母为0的可能的时候加上推断

讲的非常具体的题解：http://blog.csdn.net/morgan_xww/article/details/6776947

直接按公式写的代码就是：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;

#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-10;
const int INF = 100000000;
const int MAXN = 10000+100;

vector<int>g[MAXN];
double k[MAXN],e[MAXN];
double a[MAXN],b[MAXN],c[MAXN];
int n;

bool sea(int i, int fa)
{
    if(g[i].size() == 1 && fa!=-1)//叶子节点
    {
        a[i]=k[i];
        c[i]=b[i]=1.0-k[i]-e[i];
        return true;
    }
    //非叶子节点,此时该非叶子节点的子孙都已经遍历过了
    double aa=0.0,bb=0.0,cc=0.0;
    for(int j=0;j<g[i].size();j++)
    {
        if( g[i][j] == fa)continue;
        if(!sea(g[i][j],i))return 0;
        aa+=a[g[i][j]];
        bb+=b[g[i][j]];
        cc+=c[g[i][j]];
    }
    int m=g[i].size();
    a[i]=(k[i]+(1-k[i]-e[i])/m*aa)/(1-(1.0-k[i]-e[i])/m*bb);
    b[i]=(1.0-k[i]-e[i])/m/(1.0-(1.0-k[i]-e[i])/m*bb);
    c[i]=( (1.0-k[i]-e[i])+(1.0-k[i]-e[i])/m*cc )/(1.0 -(1.0-k[i]-e[i])/m*bb);
    return true;
}

int main()
{
    int ncase,u,v,ic=0;

    scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            g[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&k[i],&e[i]);
            k[i]/=100.0;
            e[i]/=100.0;
        }

        printf("Case %d: ",++ic);
        if(sea(1,-1) && fabs(1.0-a[1])>EPS)
            printf("%.6lf\n",c[1]/(1.0-a[1]));
        else
            printf("impossible\n");
    }
    return 0;
}

当然更好的写法还是题解上的

#include <cstdio>  
#include <iostream>  
#include <vector>  
#include <cmath>  
  
using namespace std;  
  
const int MAXN = 10000 + 5;  
  
double e[MAXN], k[MAXN];  
double A[MAXN], B[MAXN], C[MAXN];  
  
vector<int> v[MAXN];  
  
bool search(int i, int fa)  
{  
    if ( v[i].size() == 1 && fa != -1 )  
    {  
        A[i] = k[i];  
        B[i] = 1 - k[i] - e[i];  
        C[i] = 1 - k[i] - e[i];  
        return true;  
    }  
  
    A[i] = k[i];  
    B[i] = (1 - k[i] - e[i]) / v[i].size();  
    C[i] = 1 - k[i] - e[i];  
    double tmp = 0;  
      
    for (int j = 0; j < (int)v[i].size(); j++)  
    {  
        if ( v[i][j] == fa ) continue;  
        if ( !search(v[i][j], i) ) return false;  
        A[i] += A[v[i][j]] * B[i];  
        C[i] += C[v[i][j]] * B[i];  
        tmp  += B[v[i][j]] * B[i];  
    }  
    if ( fabs(tmp - 1) < 1e-10 ) return false;  
    A[i] /= 1 - tmp;  
    B[i] /= 1 - tmp;  
    C[i] /= 1 - tmp;  
    return true;  
}  
  
int main()  
{  
    int nc, n, s, t;  
  
    cin >> nc;  
    for (int ca = 1; ca <= nc; ca++)  
    {  
        cin >> n;  
        for (int i = 1; i <= n; i++)  
            v[i].clear();  
  
        for (int i = 1; i < n; i++)  
        {  
            cin >> s >> t;  
            v[s].push_back(t);  
            v[t].push_back(s);  
        }  
        for (int i = 1; i <= n; i++)  
        {  
            cin >> k[i] >> e[i];  
            k[i] /= 100.0;  
            e[i] /= 100.0;  
        }  
          
        cout << "Case " << ca << ": ";  
        if ( search(1, -1) && fabs(1 - A[1]) > 1e-10 )  
            cout << C[1]/(1 - A[1]) << endl;  
        else  
            cout << "impossible" << endl;  
    }  
    return 0;  
}