M_sea

CF113D Museum
CodeforcesLuogu分析感觉挺套路的。设 $f_{i,j}$ 表示 Petya 在点 $i$ 、Vasy...
扫描右侧二维码阅读全文
26
2019/07

CF113D Museum

Codeforces

Luogu

分析

感觉挺套路的。

设 $f_{i,j}$ 表示 Petya 在点 $i$ 、Vasya 在点 $j$ 的概率,$p_{i,j,k,l}$ 表示从 $(i,j)$ 转移到 $(k,l)$ 的概率。

那么可以列出这样的式子

$$ \displaystyle f_{i,j}=\sum_{k=1}^n\sum_{l=1}^np_{i,j,k,l}\cdot f_{k,l} $$

注意当 $i$ 为 Petya 的初始点、$j$ 为 Vasya 的初始点时式子是这样的

$$ \displaystyle f_{i,j}-1=\sum_{k=1}^n\sum_{l=1}^np_{i,j,k,l}\cdot f_{k,l} $$

那么直接高斯消元即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=484+5;

int n,m,s,t;
int id[N][N],tot=0;
vector<int> E[N];
int deg[N];
double p[N];
double a[N][N],b[N],c[N];

inline void build() {
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            id[i][j]=++tot;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j) {
            int u=id[i][j];
            --a[u][u];
            if (i!=j) a[u][u]+=p[i]*p[j];
            for (re int x:E[i])
                for (re int y:E[j]) {
                    if (x==y) continue;
                    int v=id[x][y];
                    a[u][v]+=(1-p[x])/deg[x]*(1-p[y])/deg[y];
                }
            for (re int x:E[i]) {
                if (x==j) continue;
                int v=id[x][j];
                a[u][v]+=(1.0-p[x])/deg[x]*p[j];
            }
            for (re int y:E[j]) {
                if (i==y) continue;
                int v=id[i][y];
                a[u][v]+=p[i]*(1.0-p[y])/deg[y];
            }
        }
    b[id[s][t]]=-1;
}

inline void Gauss(int n) {
    for (re int i=1;i<=n;++i) {
        int p=i;
        for (re int j=i+1;j<=n;++j)
            if (fabs(a[j][i])>fabs(a[p][i])) p=j;
        if (i!=p) swap(a[i],a[p]),swap(b[i],b[p]);
        for (re int j=1;j<=n;++j) {
            if (i==j) continue;
            double rate=a[j][i]/a[i][i];
            for (re int k=1;k<=n;++k) a[j][k]-=rate*a[i][k];
            b[j]-=rate*b[i];
        }
    }
    for (re int i=1;i<=n;++i) c[i]=b[i]/a[i][i];
}

int main() {
    n=read(),m=read(),s=read(),t=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        E[u].push_back(v),++deg[u];
        E[v].push_back(u),++deg[v];
    }
    for (re int i=1;i<=n;++i) scanf("%lf",p+i);
    build(); Gauss(n*n);
    for (re int i=1;i<=n;++i) printf("%.10lf%c",c[id[i][i]]," \n"[i==n]);
    return 0;
}
最后修改:2019 年 07 月 26 日 09 : 55 PM

发表评论