#P2373. *【高斯消元】无向图中炸弹爆炸的概率[USACO10HOL] Driving Out the Piggies G（spj）（好题
*【高斯消元】无向图中炸弹爆炸的概率[USACO10HOL] Driving Out the Piggies G（spj）（好题
Description
# P2973 [USACO10HOL] Driving Out the Piggies G题目描述
给出一张有 个点 条边的无向图。
节点1有一个炸弹，在每个单位时间内，有 的概率在这个节点炸掉，有 的概率随机选择一条出去的路到其他的节点上，去每个节点的概率相等。
问最终炸弹在每个节点上爆炸的概率。
输入格式
第一行四个整数 $N\ M\ P\ Q \ (2 \le N \le 300,1 \le M \le 44,850,1 \le P \le Q \le 10^6)$。
下来 行，每行两个整数 ，表示一条无向边。
输出格式
输出N行，每行一个保留6位小数的实数，表示每个点的爆炸概率。
输入输出样例 #1
输入 #1
2 1 1 2
1 2
输出 #1
0.666666667
0.333333333
Hint
#include<bits/stdc++.h>
using namespace std;
const int N=310;
const double eps=1e-9;
int n,m;double p,q;
bool mp[N][N];
int d[N];
double a[N][N],x[N];
void gauss()
{
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)swap(a[i],a[r]);
for(int j=1;j<=n;++j)if(j!=i)
{
double bs=a[j][i]/a[i][i];
for(int k=i;k<=n+1;++k)a[j][k]-=a[i][k]*bs;
}
}
for(int i=1;i<=n;++i)x[i]=a[i][n+1]/a[i][i];
for(int i=1;i<=n;i++)printf("%.9lf\n",x[i]);
}
int main()
{
scanf("%d%d%lf%lf",&n,&m,&p,&q);
memset(mp,0,sizeof(mp));
memset(d,0,sizeof(d));
for(int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
mp[x][y]=mp[y][x]=true;
d[x]++;d[y]++;
}
memset(a,0,sizeof(a));
a[1][n+1]=p/q;
for(int i=1;i<=n;i++)
{
a[i][i]=1;
for(int j=1;j<=n;j++)
if(mp[i][j])
a[i][j]=-(1.0-p/q)/d[j];
}
gauss();
return 0;
}
</p>