CF113D 高斯消元、dp

题目链接

https://codeforces.com/contest/113/problem/D

思路

\(k[i]=\frac{1-p[i]}{ru[i]}\)
f[i][j]表示经过i和j的次数的期望=概率
\(f[i][j]=p[i]*p[j]*f[i][j]\)
\(+k[i]*p[j]*f[u][j]\)
\(+p[i]*k[j]*f[i][v]\)
\(+k[i]*k[j]*f[u][v]\)
把右边的f[i][j]边移过去
可以用高斯消元解方程来进行dp

错误

好多细节没明白
比如f[s][s]=1
orzattack

代码

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
const int N=500;
using namespace std;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,a,b,ru[N],id[N][N];
vector<int> G[N];
double k[N],p[N],f[N][N];
void init() {
    f[id[a][b]][n*n+1]=-1;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            int sdgzy=id[i][j];
            --f[sdgzy][sdgzy];
            if(i!=j) f[sdgzy][sdgzy]+=p[i]*p[j];
            for(vector<int>::iterator x=G[i].begin();x!=G[i].end();++x) {
                for(vector<int>::iterator y=G[j].begin();y!=G[j].end();++y) {
                    if(*x==*y) continue;
                    f[sdgzy][id[*x][*y]]+=k[*x]*k[*y];
                }
            }
            for(vector<int>::iterator it=G[i].begin();it!=G[i].end();++it) {
                if(*it==j) continue;
                f[sdgzy][id[*it][j]]+=k[*it]*p[j];
            }
            for(vector<int>::iterator it=G[j].begin();it!=G[j].end();++it) {
                if(*it==i) continue;
                f[sdgzy][id[i][*it]]+=k[*it]*p[i];
            }
        }
    }
}
double ans[N];
void gauss() {
    int N=n*n;
    for(int i=1;i<=N;++i) {
        int mx=i;
        for(int j=i+1;j<=N;++j)
            if(f[j][i]>f[mx][i]&&f[j][i]!=0) mx=j;
        if(mx!=i) swap(f[i],f[mx]);
        for(int j=1;j<=N;++j) {
            if(i==j) continue;
            double p=f[j][i]/f[i][i];
            for(int k=i;k<=N+1;k++) {
                f[j][k]-=f[i][k]*p;
            }
        }
    }
    for(int i=1;i<=N;++i) f[i][i]=f[i][N+1]/f[i][i];
}
int main() {
    n=read(),m=read();
    a=read(),b=read();
    for(int i=1;i<=m;++i) {
        int x=read(),y=read();
        G[x].push_back(y);
        G[y].push_back(x);
        ru[x]++;
        ru[y]++;
    }
    for(int i=1;i<=n;++i) scanf("%lf",&p[i]);
    for(int i=1;i<=n;++i) k[i]=(1.0-p[i])/ru[i];
    for(int i=1,cnt=0;i<=n;++i)
        for(int j=1;j<=n;++j)
            id[i][j]=++cnt;
    init();
    gauss();
    for(int i=1;i<=n;++i) printf("%.10lf ",f[id[i][i]][id[i][i]]);
    return 0;
}