【题意】
炸弹从1开始运动，每次有P/Q的概率爆炸，否则等概率沿边移动，问在每个城市爆炸的概率。
【思路】
设M表示移动一次后i->j的概率。Mk为移动k次后的概率，则有：
Mk=M^k
设S={ 1,0,0,0,… }
设pi为移动i步后到对应点爆炸的概率矩阵，则有：
p0=P/Q * S
p1=P/Q * S * M1
…
p+oo=P/Q * S * Mn
则答案为：sigma{ pi },0<=i<+oo
即：
Ans=P/Q * S * sigma{ M^i } ,0<=i<+oo
根据等差数列的求和公式：
Ans= P/Q * S * (I-M^(+oo))/(I-M)
= P/Q * S * I/(I-M)
=> Ans(I-M) = P/Q * S
其中I为单位矩阵，I[j][j]=1，其余为0。
于是可以得到n个线性方程，可以使用高斯消元法求解。
注意Ans*(I-M)，所以第i个方程的第j项系数为-(1-P/Q)*Mji。
【代码】
1 #include<set> 2 #include<cmath> 3 #include<queue> 4 #include<vector> 5 #include<cstdio> 6 #include<cstring> 7 #include<iostream> 8 #include<algorithm> 9 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt) 10 #define FOR(a,b,c) for(int a=(b);a<=(c);a++) 11 using namespace std; 12 13 typedef long long ll; 14 const int N = 400; 15 const int M = 1e5+10; 16 17 ll read() { 18 char c=getchar(); 19 ll f=1,x=0; 20 while(!isdigit(c)) { 21 if(c=='-') f=-1; c=getchar(); 22 } 23 while(isdigit(c)) 24 x=x*10+c-'0',c=getchar(); 25 return x*f; 26 } 27 28 struct Edge { 29 int v,nxt; 30 }e[M]; 31 int en=1,front[N]; 32 void adde(int u,int v) 33 { 34 e[++en]=(Edge){v,front[u]}; front[u]=en; 35 } 36 37 int n,m,du[N]; 38 double P,a[N][N]; 39 40 void gause() 41 { 42 for(int i=1;i<=n;i++) 43 { 44 int r=i; 45 for(int j=i+1;j<=n;j++) 46 if(fabs(a[j][i])>fabs(a[r][i])) r=i; 47 for(int j=1;j<=n+1;j++) swap(a[i][j],a[r][j]); 48 for(int j=n+1;j>=i;j--) 49 for(int k=i+1;k<=n;k++) 50 a[k][j]-=a[k][i]/a[i][i]*a[i][j]; 51 } 52 for(int i=n;i;i--) 53 { 54 for(int j=i+1;j<=n;j++) 55 a[i][n+1]-=a[i][j]*a[j][n+1]; 56 a[i][n+1]/=a[i][i]; 57 } 58 } 59 60 int main() 61 { 62 int x,y; 63 n=read(),m=read(),x=read(),y=read(); 64 P=(double)x/y; 65 FOR(i,1,m) { 66 x=read(),y=read(); 67 adde(x,y),adde(y,x); 68 du[x]++,du[y]++; 69 } 70 FOR(u,1,n) { 71 a[u][u]=1; 72 trav(u,i) { 73 int v=e[i].v; 74 a[u][v]-=(1.0-P)/du[v]; 75 } 76 } 77 a[1][n+1]=P; 78 gause(); 79 FOR(i,1,n) 80 printf("%.9lf ",a[i][n+1]); 81 return 0; 82 }