奇迹之流WonderfloW

Nothing Replaces Hard Work!

ZOJ1509 Family(高精度,DP,拓扑排序)

| Comments

这题确实是个好题目。讲的是动物家族,每个人都有50%父亲的基因和50%母亲的基因,然后给你一张家族图,最后询问你指定的两个人中有相同的血缘关系的百分比是多少。

一开始其实是没什么想法的。就问了问老高,后来才知道,原来是个DP。 为了无后效性,所以我们必须要先进行拓扑排序,这样的话,先把祖先之间的血缘关系求出来,然后子孙后代的寻缘关系其实可以递推到子孙的其中一人与另外一人上一辈的血缘关系的。 首先dp[i][j]表示,第i个人和第j个人的基因相同的比例是多少。 然后dp[i][i]肯定是初始化为1的。 另外,从拓扑排序后的先祖开始计算DP值,那么两重for循环,i在j前面。也就是j肯定比i的备份小,那么要是j都没有父母结点的话,显然i和j是没有相似基因的。 再来看一下递推关系:dp[i][j] = dp[father[i]][j]*0.5+dp[mother[i]][j];即i和j的基因关系就等于i的父母和j的基因比例之和。

最恶心的其实就是,你有了思路以后发现还需要高精度,因为题目要求不丢失精度,并且不能有最后的多余的0. 那么就用java吧,不过我java已经不是很熟练了,就把C++写好,让薛斌照原样给我转成了java。 不过据薛斌说,这题只涉及到了乘0.5的操作,也就是除以2,那么用二进制的话,其实就是左移一位,说不定可以有一些不要高精度的C++解法。

最后要注意的就是,你有可能还会PE,因为他要求每个case后面都要输出一个空行,但是最后一个case还不能有空行。。。反正我是搞了很久。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import java.util.*;
import java.math.*;

public class Main
{
  static int N = 310;
  static BigDecimal[][] dp = new BigDecimal[N][N];
  static Vector<Integer> edge[] = new Vector[N];
  static LinkedList<Integer> myque = new LinkedList<Integer>();
  static int[] ans = new int[N];
  static boolean[] vis = new boolean[N];
  static int[] deg = new int[N];
  static int a, b, c, num, n, m;
  
  static {
      for ( int i=0; i<N; i++)
      {
          for ( int j=0; j<N; j++)
              dp[i][j] = new BigDecimal(0);
          edge[i] = new Vector<Integer>();
      }
  }
  
  public static void main(String[] args)
  {
      Scanner in = new Scanner(System.in);
      int q;
      boolean fa = false;
      while (in.hasNext())
      {
          if(fa)System.out.println();
          fa = true;
          n = in.nextInt(); m = in.nextInt();
          for ( int i=1; i<=n; i++)
          {
              edge[i].clear();
              deg[i] = 0;
          }
          for ( int i=0; i<m; i++)
          {
              a = in.nextInt();
              b = in.nextInt();
              c = in.nextInt();
              edge[a].add(c);
              edge[a].add(b);
              deg[c] ++;
              deg[b] ++;
          }
          num = 1;
          myque.clear();
          for ( int i=1; i<=n; i++)
              if (deg[i] == 0) myque.offer(i);
          topsort();
          for ( int i=1; i<=n; i++) dp[i][i] = new BigDecimal(1);
          for ( int i=n; i>=1; i--) 
          {
              for ( int j=i-1; j>=1; j--)
              {
                  int x = ans[i];
                  int y = ans[j];
                  
                  if (edge[y].size() == 0)
                  {
                      dp[x][y] = new BigDecimal(0);
                      dp[y][x] = new BigDecimal(0);
                      continue;
                  }
                  dp[x][y] = dp[x][edge[y].get(0)].multiply(new BigDecimal(0.5)).add(dp[x][edge[y].get(1)].multiply(new BigDecimal(0.5)));
                  dp[y][x] = dp[x][y];
                  //System.out.print(x+" "+y+" "+dp[x][y]+"\n");
              }
          }
          q = in.nextInt();
          for ( int i=0; i<q; i++)
          {
              a = in.nextInt();
              b = in.nextInt();
              String s = dp[a][b].movePointRight(2).toPlainString();
              //String s = dp[a][b].multiply(new BigDecimal(100)).toString();
              //notice the difference between toString() and toPlainString()
              if (s.indexOf('.') != -1) {
                  int l = s.length() - 1;
                  while (s.charAt(l) == '0') {
                      --l;
                  }
                  if (s.charAt(l) != '.') {
                      ++l;
                  }
                  s = s.substring(0, l);
              }
              System.out.print(s);
              System.out.println("%");
          }
          
      }
  }
  static void topsort()
  {
      int index;
      for ( int i=0; i<N; i++)
          vis[i] = false;
      while (myque.peek() != null)
      {
          index = myque.poll();
          if (vis[index]) continue;
          ans[num++] = index;
          vis[index] = true;
          for ( int i=0; i<edge[index].size(); i++)
          {
              int v = edge[index].get(i);
              deg[v] --;
          }
          for ( int i=1; i<=n; i++)
          {
              if (vis[i] == false && deg[i] == 0)
                  myque.offer(i);
          }
      }
  }
}