cf113D. Museum(期望 高斯消元)
程序员文章站
2022-07-09 20:46:55
题意 "题目链接" Sol 设$f[i][j]$表示Petya在$i$,$Vasya$在$j$的概率,我们要求的是$f[i][i]$ 直接列方程高斯消元即可,由于每个状态有两维,因此时间复杂度为$O(n^6)$ 注意不能从终止节点转移而来 cpp include using namespace st ......
题意
sol
设\(f[i][j]\)表示petya在\(i\),\(vasya\)在\(j\)的概率,我们要求的是\(f[i][i]\)
直接列方程高斯消元即可,由于每个状态有两维,因此时间复杂度为\(o(n^6)\)
注意不能从终止节点转移而来
#include<bits/stdc++.h> using namespace std; const int maxn = 2333; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, a, b, lim; double p[maxn], f[maxn][maxn], e[maxn][maxn], deg[maxn]; vector<int> v[maxn]; int id[maxn][maxn], tot; void pre() { f[id[a][b]][lim + 1] = -1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { int now = id[i][j]; --f[now][now];//tag if(i != j) f[now][now] += p[i] * p[j]; for(auto &x : v[i]) { for(auto &y : v[j]) { if(x == y) continue; int nxt = id[x][y]; f[now][nxt] += (1.0 - p[x]) * (1.0 - p[y]) / deg[x] / deg[y]; } } for(auto &x : v[i]) { int nxt = id[x][j]; if(x == j) continue; f[now][nxt] += (1.0 - p[x]) * p[j] / deg[x]; } for(auto &y : v[j]) { int nxt = id[i][y]; if(i == y) continue; f[now][nxt] += p[i] * (1.0 - p[y]) / deg[y]; } } } } void gauss() { for(int i = 1; i <= lim; i++) { int mx = i; for(int j = i + 1; j <= lim; j++) if(f[j][i] > f[mx][i] && f[j][i] != 0) swap(j, mx); if(mx != i) swap(f[i], f[mx]); // assert(fabs(f[i][i] < 1e-13)); for(int j = 1; j <= lim; j++) { if(i == j) continue; double p = f[j][i] / f[i][i]; for(int k = i; k <= lim + 1; k++) f[j][k] -= f[i][k] * p; } } for(int i = 1; i <= lim; i++) f[i][i] = f[i][lim + 1] / f[i][i]; } int main() { n = read(); m = read(); a = read(); b = read(); lim = n * n; for(int i = 1; i <= m; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); deg[x]++; deg[y]++; } 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++) id[i][j] = ++tot; pre(); gauss(); for(int i = 1; i <= n; i++) printf("%.10lf ", f[id[i][i]][id[i][i]]); return 0; }