欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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;
}