题意：
给出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
}