这题求的是到某个点为终点的概率
以某个点为终点的概率可以是这个状态被进入的期望次数
即f[i][j]表示第一个人到i点 第二个人到j点的进入这个状态的期望次数
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); } |