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