pku1202 Family DAG圖上的概率DP

題意：
給出N個(gè)怪物的家譜樹，求M對(duì)怪物間的相關(guān)度。怪物可能一夫多妻或一妻多夫，也可以隔代交配。

給力條件：DAG

解法：
眾所周知，DP有兩種推理方法：第i個(gè)狀態(tài)能推出哪些狀態(tài)以及第i個(gè)狀態(tài)可以由哪些狀態(tài)得出，本題必須使用第二種方案
dp[pos][i],i=1..n為第pos個(gè)節(jié)點(diǎn)與其前趨（包括間接）節(jié)點(diǎn)間的相關(guān)度。
狀態(tài)轉(zhuǎn)移即為dp[pos][i]=sum(dp[p][i]*0.5),p為pos的直接前驅(qū)趨節(jié)點(diǎn)。
這題POJ好詭異，死都過不去，但是在小poj(poj.grids.cn)，和zju上都沒問題。可能將遞歸改成拓?fù)湫蛏系牡涂梢粤恕２贿^我懶，不想動(dòng)- -

代碼：

 1import java.io.*;
 2import java.util.*;
 3import java.math.*;
 4public class Main {
 5    static int nxt[][]=new int[305][305];
 6    static BigDecimal dp[][]=new BigDecimal[305][305],two=BigDecimal.ONE.add(BigDecimal.ONE);
 7    static int n=0,m=0;
 8    static boolean used[]=new boolean[305];
 9    static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
10    static int nextInt() throws IOException
11    {
12        in.nextToken();
13        return (int)in.nval;
14    }
15    static void dfs(int pos)
16    {
17        if(used[pos]) return;
18        used[pos]=true;
19        
20        for(int j=0;j<2&&nxt[pos][j]!=-1;j++)
21        {
22            int p=nxt[pos][j];
23            dfs(p);
24            for(int i=1;i<=n;i++)  {dp[pos][i]=dp[pos][i].add(dp[p][i].divide(two));dp[i][pos]=dp[pos][i];}
25        }
26        dp[pos][pos]=BigDecimal.ONE;
27    }
28    public static void main(String[] args) throws IOException{
29        n=nextInt();
30         m=nextInt();
31        nxt=new int[n+1][2];
32        used=new boolean[n+1];
33        dp=new BigDecimal[n+1][n+1];
34        for(int i=1;i<=n;i++)
35        {
36            Arrays.fill(dp[i],BigDecimal.ZERO);
37            Arrays.fill(nxt[i],-1);
38        }
39        Arrays.fill(used, false);
40        for(int i=0;i<m;i++)
41        {
42            int a=nextInt(),b=nextInt(),c=nextInt();
43            nxt[a][0]=b;
44            nxt[a][1]=c;
45        }
46        for(int i=1;i<=n;i++)
47            dfs(i);
48       m=nextInt();
49       for(int i=0;i<m;i++)
50       {
51           int a=nextInt(),b=nextInt();
52          System.out.println(dp[a][b].multiply(new BigDecimal("100")).stripTrailingZeros().toPlainString()+"%");
53       }
54    }
55}

posted on 2011-02-05 20:59 yzhw 閱讀(307) 評(píng)論(0)  編輯 收藏 引用 所屬分類: DP 、graph