SRM537-div2-3-PrinceXToastbook

zz: http://www.strongczq.com/2012/03/srm537-div2-3-princextoastbook.html

題目原文：http://community.topcoder.com/stat?c=problem_statement&pm=11356

題目大意：      有人買了N本面包書，編号為0,1,...,N-1。每本面包書都含有一些知識。吃掉一本面包書有可能可以獲得其中的知識。面包書之間會存在知識依賴關系，用int[]  p來表示,如果面包書i依賴于面包樹j，則p[i]=j，如果取值為-1則說明該書不依賴于其他書。如果吃一本面包書時已經掌握了它所依賴的書的知識，那麼就可以獲得該書的知識，否則不可以。現在按照随機順序吃這些書，問最終獲得的幾本書的知識的期望值是多少。

    資料規模：N的取值範圍為[2,50]    

思路：      根據題目的描述，每一本書其實都存在一條知識依賴路徑，例如假設對于書i，存在以下路徑：      i1 -> i2 -> i3 -> i 那麼i依賴于i3, i3依賴于i2, i2依賴于i1，i1不依賴于其他書。擷取i的唯一條件是吃書的順序必須是按着箭頭的順序吃。并且如果這條路徑存在環形結構，那麼i的知識必然無法獲得。      根據以上分析，我們可以對每一本書計算其知識被擷取的機率。也就是說，對于書i，它的依賴路徑上的所有書（包括自己）在随機排列中正好按照依賴順序排的機率。如果依賴路徑的長度為n，則該機率值為1/n! 。把所有書的機率值相加就是最終期望值。      寫代碼的時候也特别注意閉環依賴的判斷。本人第一遍代碼中，判斷i存在環形依賴的條件是依賴路徑重新回到i。由于環形依賴的閉環口未必是在i上，例如 i3 -> i1 -> i2 -> i3 -> i，i3是閉環口，是以判斷條件不正确。解決辦法是，可以使用一個boolean數組來記錄每一個節點是否已存在于依賴路徑來找閉環。

Java代碼：

public class PrinceXToastbook
{
      public double eat(int[] p)
      {
            double res = 0.0;
            for(int i = 0; i < p.length; ++i){
                  int len = 1;
                  int pp = p[i];
                  boolean[] visit = new boolean[p.length];
                  visit[i] = true;
                  while(pp != -1 && !visit[pp]){
                        visit[pp] = true;
                        pp = p[pp];
                        len++;
                  }
                  if(pp != -1){
                        continue;
                  }
                  double prop = 1.0;
                  for(int j = 1; j <= len; ++j){
                        prop /=j;
                  }
                  res += prop;
            }
            return res;
      }
}