自动搬运

查看原文

来自洛谷，原作者为

	jun头吉吉 alive

搬运于2025-08-24 21:43:59，当前版本为作者最后更新于2020-07-28 13:54:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P2973 [USACO10HOL]Driving Out the Piggies G

题意

给出一张$n$个点，$m$条边的无向图，节点$1$有一个炸弹，在每个单位时间内，有$\dfrac {p}{ q}$的概率在这个节点炸掉，有$1-\dfrac{p}q$的概率随机选择一条出去的路到其他的节点上，去每个节点的概率相等。问最终炸弹在每个节点上爆炸的概率。

题解

考场上做到这道题，一脸蒙蔽

我们看一下下面这个与本题无关例子：

小明、小红、小芳在通过手心手背的游戏来决定哪两个人先出场，若有两个人同时出手心或手背那就让那两个人出场，否则重复游戏。问：小明与小红先出场的概率是多少？

很容易地我们知道，第一局有$\dfrac 1 4$的可能是小明与小红先出场，也有可能是$\dfrac14$的概率重开一局，再下一局也是如此。因此我们可以设小明与小红先出场的概率为$x$，显然：

$$x=\frac14+\frac14x$$

那么这两题有什么相同点呢？由于两题都没有限制次数，因此我们无法通过有限次便利得到答案。那我们就根据上一题的方法：设未知数

我们假设到第$i$个点的概率为$x_i$，入度为$d_i$，那么考虑其是炸弹可以从哪里来：

• 如果这个点是$1$号点，那么其概率是一开始的炸弹爆炸或者是与它相连的点的如果不爆炸就会炸弹就有可能转一到这个点，即：

$$x_1=\dfrac pq+\sum_{(1,j)\in E}x_j \times (1-\dfrac p q)\times\dfrac 1 d_j $$

• 如果这个点是其他点，那就只能从相邻的点转移过来

$$x_i=\sum_{(i,j)\in E}x_j \times (1-\dfrac p q)\times\dfrac 1 d_j $$

式中$p$、$q$、$d$均为常数，因此所有的柿子可以组成一个$n$元一次方程组然后就到了我们喜闻乐见的手解300元方程高斯消元的过程了

#include<bits/stdc++.h> 
#define maxn 310
#define eps (1e-6)
using namespace std;
int n,m,p,q,x,y;
int f[310][310];
int in[310];
double a[maxn][maxn];
void gauss_jordan(){
	for(int i=1;i<=n;++i){
		int r=i;
		for(int j=i+1;j<=n;++j)
			if(fabs(a[r][i])<fabs(a[j][i]))
				r=j;
		if(r!=i)
			for(int j=1;j<=n+1;++j)
			swap(a[i][j],a[r][j]);
			for(int j=1;j<=n;++j)if(j!=i){
		 		double tmp=a[j][i]/a[i][i];
		 		for(int k=i+1;k<=n+1;++k)
	   		   		a[j][k]-=a[i][k]*tmp;
			}
   	}
	for(int i=1;i<=n;++i)
		a[i][n+1]/=a[i][i];
}
int main(){
	//freopen("dotp.in","r",stdin);
	//freopen("dotp.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&p,&q);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		f[x][y]=f[y][x]=true;
		in[x]++;in[y]++;
	}
	a[1][n+1]=1.0*p/q;
	for(int i=1;i<=n;i++){
		a[i][i]=1;
		for(int j=1;j<=n;j++)
			if(f[i][j])
				a[i][j]=-(1-(double)p/q)/in[j];
	}
	gauss_jordan();
	for(int i=1;i<=n;i++)
		printf("%.9lf\n",a[i][n+1]);
	return 0;
}