【题解】臭气弹

用次数乘上 \(P/Q\) 来构建增广矩阵，进行高斯消元。在算出每个点被摧毁的概率与所有点的期望出现次数。

由于每个点爆炸概率相同，所以每个点被摧毁的概率就是这个点的期望出现次数 \(/\) 所有点的期望出现次数。

#include<bits/stdc++.h>
using namespace std;
const int N=311;
const double esp=1e-8;
int n,m,p,q;
double sum,c[N][N],d[N],a[N][N],b[N],o[N];
//int h[N],cnt;
//struct node{int to,next,y;}e[N];
//inline void add(int x,int y){
//	e[++cnt].to=y;e[cnt].next=h[x];
//	h[x]=cnt;
//}
inline void zzd(int &maxx,int i){
	for(int j=i+1;j<=n;++j){//找系数最大值 
		if(fabs(c[j][i])>fabs(c[maxx][i]))
			maxx=j;
	}
	return ;
}
signed main(void){
	scanf("%d%d%d%d",&n,&m,&p,&q);
	double tt=1.0-(1.0*p/q);
	for(int x,y,i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
//		add(x,y);add(y,x);
		c[x][y]=c[y][x]=1;
		++d[x],++d[y];
	}
	for(int i=1;i<=n;++i){
		a[i][i]=1.0;
		for(int j=1;j<=n;++j){
			if(c[i][j]){
				a[i][j]-=1.0*tt/d[j];//概率 
				//if(j!=t) a[j][i]-=1.0*tt/d[j+t];
			}
		}
	}
	b[1]=1.0;
	for(int maxx,i=1;i<=n;++i){
		maxx=i;
		zzd(maxx,i);
		for(int j=1;j<=n;++j) swap(a[i][j],a[maxx][j]);
		swap(b[i],b[maxx]);
		for(int j=1;j<=n;++j){
			if(j!=i){
				tt=a[j][i]/a[i][i];
				for(int k=i;k<=n;++k)
					a[j][k]-=a[i][k]*tt;
				b[j]-=b[i]*tt;
			}
		}
	}
	for(int i=1;i<=n;++i){
		o[i]+=b[i]/a[i][i];
		sum+=o[i];
	}
	for(int i=1;i<=n;++i)
		printf("%.9lf\n",o[i]/sum);//每个概率/总概率 
	return 0;
}