Dragster

Dragster competitions are elimination tournaments, where each confrontation consists of two competitors racing side by side and only one of them being declared the winner (the fastest one, obviously). The winners are then rematched into new races, until only one competitor remains - which is declared the winner.

Rubens is an experienced pilot, with a racing career in several categories, including Formula 1. However, after facing some difficulties, he decided to dedicate himself to dragster racing. Using his vast experience from Formula 1, he can, observing the competitors, tell what is the probability each one would prevail during a race between any pair of them.

Even though Rubens is a good pilot, he's not very good in math nor computing, so he asked your help to write a program that, given the probabilities computed by Rubens for all races between each pair of pilots, and the description of the tournament structure, determines his proability of winning the tournament.

Input 

The input consists of several test cases. The first line of a test case contains a single integer N, indicating the number of competitors in this tournament ( 2N300). In the tournament descripton, each competitor is identified by an integer from 1 to N, and the races are identified by integers from N + 1 to 2 x N - 1. Rubens is always identified by the number 1. The N next lines describe the probability matrix computed by Rubens. The i-th line contains N real numbers M[i, j] separated by spaces ( 0M[i, j]1, for 1iN and 1jN). Each matrix entry M[i, j] indicates the probability of competitor i winning a race against competitor j ( 0.001M[i, j]0.999 and M[i, j] + M[j, i] = 1 for ij , and M[i, j] = 0 for i = j). The probabilities will always be given with three decimal places. Each one of the next N - 1 lines contains two integers A, B, describing a race. A and B are race or competitor identifiers ( 1A2 x N - 1 e 1B2 x N - 1). The first of these lines describes race N + 1, the next line describes race N + 2, and so on. When a race identifier k appears in the input as A, that means the winner of race k will run against B; similarly, when a race identifier k appears as B, the winner of race k will run against A.

The end of input is indicated by a line containing a single zero.

Output 

Sample Input 

4
0.000 0.500 0.400 0.400
0.500 0.000 0.500 0.500
0.600 0.500 0.000 0.600
0.600 0.500 0.400 0.000
1 2
3 4
5 6
5
0.000 0.500 0.600 0.600 0.001
0.500 0.000 0.500 0.500 0.500
0.400 0.500 0.000 0.500 0.500
0.400 0.500 0.500 0.000 0.500
0.999 0.500 0.500 0.500 0.000
3 8
9 6
4 5
1 2
0

Sample Output 

0.200000
0.225125

題目描述：

給 n 名選手的獲勝機率，選手 i 勝過選手 j 的機率為 M[i, j]。

並且給比賽的樹枝狀賽程圖，問最後選手 1 勝出的機率為何 ?

題目解法：

模擬，計算機率

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n;
double A[705][705];
int L[705], R[705];
vector< pair<int, double> > dfs(int races) {
    vector< pair<int, double> > ret;
    if(races <= n) {
        ret.push_back(make_pair(races, 1));
        return ret;
    }
    vector< pair<int, double> > l = dfs(L[races]);
    vector< pair<int, double> > r = dfs(R[races]);
    for(int i = 0; i < l.size(); i++) {
        double p = 0;
        for(int j = 0; j < r.size(); j++)
            p += l[i].second * r[j].second * A[l[i].first][r[j].first];
        ret.push_back(make_pair(l[i].first, p));
    }
    for(int i = 0; i < r.size(); i++) {
        double p = 0;
        for(int j = 0; j < l.size(); j++)
            p += l[j].second * r[i].second * A[r[i].first][l[j].first];
        ret.push_back(make_pair(r[i].first, p));
    }
    return ret;
   
}
int main() {
    while(scanf("%d", &n) == 1 && n) {
        int i, j;
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                scanf("%lf", &A[i][j]);
        int indeg[705] = {};
        for(i = n + 1; i < 2*n; i++) {
            scanf("%d %d", &L[i], &R[i]);
            indeg[L[i]]++, indeg[R[i]]++;
        }
        vector< pair<int, double> > ret;
        for(i = 1; i < 2*n; i++) {
            if(indeg[i] == 0) {
                ret = dfs(i);
                break;
            }
        }
        for(i = 0; i < ret.size(); i++)
            if(ret[i].first == 1)
                printf("%.6lf\n", ret[i].second);
    }
    return 0;
}