博物馆(museum)

发表于由

这题求的是到某个点为终点的概率
以某个点为终点的概率可以是这个状态被进入的期望次数
即f[i][j]表示第一个人到i点 第二个人到j点的进入这个状态的期望次数
12
p是停留在某个点的概率 d是某个点的度数 S1 S2是初始状态
这个方程有环
所以用高斯消元做
把每个fij看成一个元 拿去解方程 即可出解

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

struct line
{
    int to, next;
}li[1005];

int n, m, a, b, be[25], d[25], to[1005][2], fr[25][25], tot, l;
double p[25], v[405][405], ans[405];

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 0; i < m; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
        ++d[fr], ++d[to];
    }
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            fr[i][j] = tot;
            to[tot][0] = i, to[tot][1] = j;
            ++tot;
        }
    for (int i = 0; i < tot; ++i)
    {
        int u1 = to[i][0], u2 = to[i][1];
        v[i][i] = -1 ;
        if (u1 == u2) continue;
        v[i][i] += p[u1] * p[u2];
        double va1 = p[u1] * (1 - p[u2]) / d[u2],
                     va2 = (1 - p[u1]) * p[u2] / d[u1],
                     va = (1 - p[u1]) * (1 - p[u2]) / d[u1] / d[u2];

        for (int j1 = be[u2]; j1; j1 = li[j1].next)
            v[fr[u1][li[j1].to]][i] = va1;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            v[fr[li[j1].to][u2]][i] = va2;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            for (int j2 = be[u2]; j2; j2 = li[j2].next)
                v[fr[li[j1].to][li[j2].to]][i] = va;
    }
    v[fr[a][b]][tot] = -1;/*
    for (int i = 0; i < tot; ++i)
    {
        for (int j = 0; j <= tot; ++j) printf("%.2f ", v[i][j]);
        printf("\n");
    }*/
    for (int i = 0; i < tot; ++i)
    {
        int t = -1;
        for (int j = i; j < tot; ++j)
            if (t == -1 || abs(v[j][i]) > abs(v[t][i]))
                t = j;
        for (int j = 0; j <= tot; ++j)
            swap(v[i][j], v[t][j]);
        for (int j = i + 1; j < tot; ++j)
        {
            double va = v[j][i] / v[i][i];
            for (int k = i; k <= tot; ++k)
                v[j][k] -= va * v[i][k];
        }
    }
    for (int i = tot - 1; i >= 0; --i)
    {
        for (int j = i + 1; j < tot; ++j)
            v[i][tot] -= ans[j] * v[i][j];
        ans[i] = v[i][tot] / v[i][i];
    }/*
    for (int i = 0; i < tot; ++i)
        printf("%.6f ", ans[i]);
        printf("\n");*/
    for (int i = 1; i <= n; ++i)
        printf("%.6f ", ans[fr[i][i]] + 1e-8);
    fclose(stdin);fclose(stdout);
}

发表评论