Description
有一天Petya和他的朋友Vasya在进行他们众多旅行中的一次旅行，他们决定去参观一座城堡博物馆。这座博物馆有着特别的样式。它包含由m条走廊连接的n间房间，并且满足可以从任何一间房间到任何一间别的房间。
两个人在博物馆里逛了一会儿后两人决定分头行动，去看各自感兴趣的艺术品。他们约定在下午六点到一间房间会合。然而他们忘记了一件重要的事：他们并没有选好在哪儿碰面。等时间到六点，他们开始在博物馆里到处乱跑来找到对方（他们没法给对方打电话因为电话漫游费是很贵的）
不过，尽管他们到处乱跑，但他们还没有看完足够的艺术品，因此他们每个人采取如下的行动方法：每一分钟做决定往哪里走，有Pi 的概率在这分钟内不去其他地方（即呆在房间不动），有1-Pi 的概率他会在相邻的房间中等可能的选择一间并沿着走廊过去。这里的i指的是当期所在房间的序号。在古代建造是一件花费非常大的事，因此每条走廊会连接两个不同的房间，并且任意两个房间至多被一条走廊连接。
两个男孩同时行动。由于走廊很暗，两人不可能在走廊碰面，不过他们可以从走廊的两个方向通行。（此外，两个男孩可以同时地穿过同一条走廊却不会相遇）两个男孩按照上述方法行动直到他们碰面为止。更进一步地说，当两个人在某个时刻选择前往同一间房间，那么他们就会在那个房间相遇。
两个男孩现在分别处在a，b两个房间，求两人在每间房间相遇的概率。
Input
第一行包含四个整数，n表示房间的个数;m表示走廊的数目;a,b (1 ≤ a, b ≤ n),表示两个男孩的初始位置。
之后m行每行包含两个整数，表示走廊所连接的两个房间。
之后n行每行一个至多精确到小数点后四位的实数 表示待在每间房间的概率。
题目保证每个房间都可以由其他任何房间通过走廊走到。
Output
输出一行包含n个由空格分隔的数字，注意最后一个数字后也有空格，第i个数字代表两个人在第i间房间碰面的概率（输出保留6位小数）
注意最后一个数字后面也有一个空格
Sample Input
2 1 1 2
1 2
0.5
0.5
1 2
0.5
0.5
Sample Output
0.500000 0.500000
HINT
对于100%的数据有 n <= 20，n-1 <= m <= n(n-1)/2
Solution
虽然是个sb题但是$1A$就很得劲了。因为省的调了
设$ans_{x,y}$表示第一个人在$x$点，第二个人在$y$点的概率。同时设$fx,fy$分别为$x$和$y$的相邻点，$d_i$表示$i$点的度数。
那么就有公式
$ans_{x,y}=p_x\times p_y\times ans_{x,y}$（两个人都停在原地）
$~~~~~~~~~~~~~~+(1-p_x)\times(1-p_y)\times\sum ans_{fx,fy}\times\frac{1}{d_{fx}\times d_{fy}}$（两个人都走）
$~~~~~~~~~~~~~~+p_x\times(1-p_y)\times\sum ans_{x,fy}\times\frac{1}{d_{fy}}$（只有第二个人走）
$~~~~~~~~~~~~~~+(1-p_x)\times p_y\times\sum ans_{fx,y}\times\frac{1}{d_{fx}}$（只有第一个人走）
把每一个$ans_{x,y}$看做一个未知数，然后就可以列出来$n^2$个方程组。高斯消元一下就可以求出来每一个$ans_{x,y}$了。
注意构造矩阵的时候可能状态$(fx,fy)$已经结束了（也就是$fx=fy$）所以不能从那里转移来。
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#define N (409)
using namespace std; struct Node{int x,y;}A[N];
struct Edge{int to,next;}edge[N];
double f[N][N],ans[N],p[N];
int n,m,s,e,u,v,c,id_num,id[N][N];
int head[N],Ind[N],num_edge; void add(int u,int v)
{
Ind[v]++;
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} void Build()
{
for (int i=; i<=c; ++i)
{
int x=A[i].x,y=A[i].y;
if (x!=y) f[i][i]=(-p[x]*p[y]);
else f[i][i]=;
for (int j=head[x]; j; j=edge[j].next)
for (int k=head[y]; k; k=edge[k].next)
{
int fx=edge[j].to,fy=edge[k].to;
if (fx==fy) continue;
f[i][id[fx][fy]]=-1.0/(Ind[fx]*Ind[fy])*(-p[fx])*(-p[fy]);
}
for (int j=head[x]; j; j=edge[j].next)
{
int fx=edge[j].to;
if (fx==y) continue;
f[i][id[fx][y]]=-1.0/(Ind[fx])*(-p[fx])*p[y];
}
for (int j=head[y]; j; j=edge[j].next)
{
int fy=edge[j].to;
if (x==fy) continue;
f[i][id[x][fy]]=-1.0/(Ind[fy])*p[x]*(-p[fy]);
}
if (x==s && y==e) f[i][c+]=;
}
} void Gauss()
{
for (int i=; i<=c; ++i)
{
int num=i;
for (int j=i+; j<=c; ++j)
if (fabs(f[j][i])>fabs(f[num][i])) num=j;
if (num!=i) swap(f[i],f[num]);
for (int j=i+; j<=c; ++j)
{
double t=f[j][i]/f[i][i];
for (int k=i; k<=c+; ++k)
f[j][k]-=t*f[i][k];
}
}
for (int i=c; i>=; --i)
{
for (int j=i+; j<=c; ++j)
f[i][c+]-=f[i][j]*ans[j];
ans[i]=f[i][c+]/f[i][i];
}
} int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
for (int i=; i<=m; ++i)
{
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
for (int i=; i<=n; ++i)
scanf("%lf",&p[i]);
for (int i=; i<=n; ++i)
for (int j=; j<=n; ++j)
{
id[i][j]=++c;
A[c]=(Node){i,j};
}
Build();
Gauss();
for (int i=; i<=n; ++i)
printf("%.6lf ",ans[id[i][i]]);
}