題意：
給出N個怪物的家譜樹，求M對怪物間的相關度。怪物可能一夫多妻或一妻多夫，也可以隔代交配。
給力條件：DAG
解法：
眾所周知，DP有兩種推理方法：第i個狀態能推出哪些狀態以及第i個狀態可以由哪些狀態得出，本題必須使用第二種方案
dp[pos][i],i=1..n為第pos個節點與其前趨（包括間接）節點間的相關度。
狀態轉移即為dp[pos][i]=sum(dp[p][i]*0.5),p為pos的直接前驅趨節點。
這題POJ好詭異，死都過不去，但是在小poj(poj.grids.cn)，和zju上都沒問題。可能將遞歸改成拓撲序上的迭代就可以了。不過我懶，不想動- -
代碼：
1
import java.io.*;
2import java.util.*;
3import java.math.*;
4
public 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
}