用二进制表示是否已经被吃掉,最后输出所有只剩下一个的状态。
要注意的是状态转移时候的概率要除以所有可能转移数才是正确的概率
1
2 const int N = 19;
3 #define bin(x) (1 << (x))
4 #define L(x) ((x) << 1)
5 #define R(x) ((x) >> 1)
6 #define low(x) ((x) & (-x))
7 double g[N][N];
8 double prob[bin(N)];
9 int n, full;
10 int main()
11 {
12 int i,j,s;
13 scanf("%d", &n);
14 for (i = 0;i < n;i++) {
15 for (j = 0;j < n;j++) {
16 scanf("%lf", &g[i][j]);
17 }
18 }
19 full = bin(n) - 1;
20 prob[full] = 1.0;
21 for (s = full;s > 0;s--) {
22 double bit = countbit(s);
23 bit = bit * (bit - 1) / 2;
24 for (i = 0;i < n;i++) { if (!(s & bin(i))) { continue; }
25 for (j = i + 1;j < n;j++) { if (!(s & bin(j))) { continue; }
26 prob[s - bin(j)] += prob[s] * g[i][j] / bit;
27 prob[s - bin(i)] += prob[s] * g[j][i] / bit;
28 }
29 }
30 }
31 for (i = 0;i < n;i++) {
32 printf("%.6f ", prob[bin(i)]);
33 }
34 putchar(10);
35 return 0;
36 }
37