luogu P2973 [USACO10HOL]Driving Out the Piggies G 驱逐猪猡

问题是在1时刻有个炸蛋在1号点这个炸弹有p/q的概率爆炸如果没有爆炸那么会有1/di的概率选择一条边跳到另外一个点上重复这个过程。

问炸弹在第i号点上爆炸的概率。

一个比较传统的在图上期望的题目。考虑每一秒都有p/q的概率爆炸所以当秒数过大的时候我们可以忽略不记概率了。

但是这要求需要求出每一秒炸弹在某个点的概率。

设T矩阵当前时刻炸弹在某个点的概率显然一开始T={1,0,0,...};

可以发现在第二秒的时候设W矩阵为由i点到j点转移的概率。

T=T×W.在第二秒的时候炸弹爆炸的概率s为\(\frac{p}{q}(1-\frac{p}{q})\) 那么此时在各点爆炸的概率为s×T.

综上将答案矩阵ans写出来 \(ans=\frac{p}{q}\cdot T+\frac{p}{q}\cdot T\cdot W\cdot (1-\frac{p}{q})+\frac{p}{q}\cdot T\cdot W^2\cdot (1-\frac{p}{q})^2+...\)

设 \(W=W\cdot (1-\frac{p}{q})\)

\(ans=\frac{p}{q}\cdot T+\frac{p}{q}\cdot T\cdot W+\frac{p}{q}\cdot T\cdot W^2+...\)

可以发现把公因数提出来然后广义矩阵等比数列求和。

\(ans=\frac{p}{q}\cdot T\cdot \frac{I-W^{\infty}}{I-W}\)

可以直接将\(W^{\infty}\)给忽略掉因为显然趋近于0.

\((I-W)\cdot ans=\frac{p}{q}\cdot T\)

I为单位矩阵 W为已知矩阵 T为已知矩阵差ans.

不难想到高斯消元.

坑点列矩阵的时候 W得倒着列因为考虑一下W的列相加为右边的T.并非行相加。

所以我们将行列互换一下才行。wa了半天...

const int MAXN=310;

int n,m;

int a[MAXN][MAXN],d[MAXN];

db p,q,b[MAXN][MAXN],f[MAXN];

inline void GAUSS()

{

	rep(1,n,i)

	{

		int p=i;

		rep(i+1,n,j)if(fabs(b[j][i])>fabs(b[p][i]))p=j;

		if(p!=i){rep(1,n,j)swap(b[p][j],b[i][j]);swap(f[p],f[i]);}

		rep(1,n,j)

		{

			if(i==j)continue;

			db d=b[j][i]/b[i][i];

			rep(1,n,k)b[j][k]-=b[i][k]*d;

			f[j]-=f[i]*d;

		}

	}

	rep(1,n,i)f[i]=f[i]/b[i][i];

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(m);p=read();q=read();

	rep(1,m,i)

	{

		int get(x);int get(y);

		a[y][x]=a[x][y]=1;++d[x];++d[y];

	}

	rep(1,n,i)

	{

		rep(1,n,j)

		{

			if(i==j)b[i][j]=1;

			else if(a[i][j])b[i][j]=-(1.0/d[j])*(1.0-p/q);

		}

	}

	f[1]=p/q;GAUSS();

	rep(1,n,i)printf("%.9lf\n",f[i]);

	return 0;

}

巴特西

luogu P2973 [USACO10HOL]Driving Out the Piggies G 驱逐猪猡

最新文章

热门文章