题目链接

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;

}