题目大意：给定一张无向连通图，两个人初始各在某个点上，每个时刻每个人会不动或任选出边走，求两人最终期望在哪里相遇
把点数平方，原图上的两个点(x,y)变成新图上的一个点
然后令A为这个图的邻接矩阵(若两人在同一点上则没有出边，否则按概率转移)，S为初始行向量(S[(a,b)]=1)，ans为答案行向量
那么有ans=S+SA+SA^2+SA^3+…
=S(I-A^+∞)/(I-A)
=S/(I-A)
于是有ans*(I-A)=S
于是对I-A的转置求高斯消元即可。
和驱逐猪猡那题的思路很像。
#include <cmath>#include <cstdio>#include <cstring>#include <iomanip>#include <iostream>#include <algorithm>#define M 440#define P(x,y) ((x)*n-n+(y))using namespace std;struct abcd{int to,next;}table[M];int head[M],tot;int n,m,a,b;int degree[M];long double p[M],f[M][M],ans[M];void Add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void Gauss_Elimination(int n){int i,j,k;for(i=1;i<=n;i++){k=i;for(j=i;j<=n;j++)if(fabs(f[j][i])>fabs(f[k][i]))k=j;for(j=i;j<=n+1;j++)swap(f[i][j],f[k][j]);for(k=i+1;k<=n;k++){long double temp=-f[k][i]/f[i][i];for(j=i;j<=n+1;j++)f[k][j]+=f[i][j]*temp;}}for(i=n;i;i–){for(j=i+1;j<=n;j++)f[i][n+1]-=f[i][j]*ans[j];ans[i]=f[i][n+1]/f[i][i];}}bool Compare(int x,int y){return ans[P(x,x)] < ans[P(y,y)];}int main(){//freopen("electric.in","r",stdin);//freopen("electric.out","w",stdout);int i,j,x,y;cin>>n>>m>>a>>b;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);degree[x]++;degree[y]++;Add(x,y);Add(y,x);}for(i=1;i<=n;i++)cin>>p[i];for(x=1;x<=n;x++)for(y=1;y<=n;y++)if(x!=y){f[P(x,y)][P(x,y)]-=p[x]*p[y];for(i=head[x];i;i=table[i].next)f[P(x,y)][P(table[i].to,y)]-=(1-p[x])/degree[x]*p[y];for(j=head[y];j;j=table[j].next)f[P(x,y)][P(x,table[j].to)]-=(1-p[y])/degree[y]*p[x];for(i=head[x];i;i=table[i].next)for(j=head[y];j;j=table[j].next)f[P(x,y)][P(table[i].to,table[j].to)]-=(1-p[x])*(1-p[y])/degree[x]/degree[y];}for(i=1;i<=n*n;i++)for(j=1;j<i;j++)swap(f[i][j],f[j][i]);for(i=1;i<=n*n;i++)f[i][i]+=1;f[P(a,b)][n*n+1]=1;Gauss_Elimination(n*n);for(i=1;i<=n;i++)cout<<fixed<<setprecision(6)<<ans[P(i,i)]<<' ';return 0;}
，那段雨骤风狂。人生之旅本就是风雨兼程，是要说曾经拥有，
