UAPC 2011 H World domination

問題

n個の敵がいる。
それぞれの敵は、どれか一人の他の敵の、弱点になるパーツを持っている。
パーツは一人一つで、弱点がかぶっていることはない。

弱点のパーツを持っていないときに、その敵を1ターンで倒せる確率はp[i],
持っているときにその敵を1ターンで倒せる確率はw[i]である。

どのような順序で敵を倒せば、かかるターン数の期待値が最小になるか。
期待値の最小値を求めよ。また、そのような期待値を実現する倒し方の総数を求めよ。

方針

弱点の関係を表すグラフはいくつかの輪からなるものである。
輪の一体の敵を倒したあとその輪の中で、弱点ではない別の敵を倒す意味はない。
（p[i]＜w[i]だから）

なので、最初の一体を決めたら、その輪の敵全員を倒すのにかかるターンの期待値は求まる。
これを全ての輪について求め足し合わせて、ついでにその場合の数も数える。

ソースコード

const int mod=100000007;
int n,e[100],C[101][101];
double p[100],q[100];
bool v[100];

void _(vi &tmp,int c){
  v[c]=1; tmp.pb(c);
  if(!v[e[c]])_(tmp,e[c]);
}
double rec(int c,int s,bool start=1){
  if(start)return 1/p[c]+rec(e[c],s,0);
  return 1/q[c]+(e[c]!=s?rec(e[c],s,0):0);
}

int main(){
  rep(i,101)rep(j,i+1)C[i][j]=(i==0||j==i?1:C[i-1][j]+C[i-1][j-1])%mod;

  while(cin>>n,n){
    rep(i,n){
      int t; cin>>p[i]>>t>>q[i];
      e[t]=i; v[i]=0;
    }
    vector<vi> vs;
    
    rep(i,n)if(!v[i]){
      vi tmp;
      _(tmp,i);
      vs.pb(tmp);
    }
    
    ll comb=1; double ex=0;
    rep(i,vs.size()){
      double mn=1e9,tmp; int cnt=0;
      rep(j,vs[i].size()){
        tmp=rec(vs[i][j],vs[i][j]);
        if(tmp+1e-9<mn)mn=tmp, cnt=0;
        if(abs(tmp-mn)<1e-9)cnt++;
      }
      ex+=mn; (comb*=cnt*C[n][vs[i].size()])%=mod;
      n-=vs[i].size();
    }
    printf("%.9f %d\n",ex,(int)comb);
  }
  return 0;
}