嘟嘟嘟
某谷又恶意评分，这题就是一个紫题吧……
这种概率期望的题做多了思路就来的特别快。令(f[i][j])表示姓P的在点(i)，姓V的在点(j)的概率，转移的时候考虑这俩哥们动不动地儿就行了：$$f[i][j] = p_i * p_j * f[i][j] + p_i * sum frac{1 - p_k}{du[k]} * f[i][k] + p_j * sum frac{1 - p_k}{du[k]} * f[k][j] + sum sum frac{1 - p_k}{du[k]} frac{1 - p_h}{du[h]} * f[k][h]$$
这样有(n ^ 2)个未知数，高斯消元(O(n ^ 6))可解。
答案就是(f[i][i])。
需要注意的是初始化(f[a][b] = 1)。然后(f[i][i])是终止节点，不能转移到其他节点，但是能从其他节点转移过来。（别忘了(f[a][b])和其他节点一样，也要转移，概率不一定就是1）
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<assert.h>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 25;
const int maxN = 505;
In ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m, A, B, cnt;
db p[maxn];
struct Edge
{
int nxt, to;
}e[maxn * maxn * 2];
int head[maxn], ecnt = -1, du[maxn];
In void addEdge(int x, int y)
{
++du[x];
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
In int N(int x, int y) {return (x - 1) * n + y;}
db f[maxN][maxN], ans[maxN];
In void init()
{
f[N(A, B)][cnt + 1] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
int u = N(i, j);
f[u][u] = 1;
if(i ^ j) f[u][u] -= p[i] * p[j];
for(int k = head[j], v; ~k; k = e[k].nxt)
if((v = e[k].to) ^ i) f[u][N(i, v)] -= p[i] * (1 - p[v]) / du[v];
for(int k = head[i], v; ~k; k = e[k].nxt)
if((v = e[k].to) ^ j) f[u][N(v, j)] -= p[j] * (1 - p[v]) / du[v];
for(int k = head[i], v1; ~k; k = e[k].nxt)
for(int h = head[j], v2; ~h; h = e[h].nxt)
if((v1 = e[k].to) ^ (v2 = e[h].to))
f[u][N(v1, v2)] -= (1 - p[v1]) * (1 - p[v2]) / du[v1] / du[v2];
}
}
In void Gauss()
{
for(int i = 1; i <= cnt; ++i)
{
int pos = i;
for(int j = i + 1; j <= cnt; ++j)
if(fabs(f[j][i]) > fabs(f[pos][i])) pos = j;
if(pos ^ i) swap(f[pos], f[i]);
if(fabs(f[i][i]) < eps) continue;
db tp = f[i][i];
for(int j = i; j <= cnt + 1; ++j) f[i][j] /= tp;
for(int j = i + 1; j <= cnt; ++j)
{
db tp = f[j][i];
for(int k = i; k <= cnt + 1; ++k) f[j][k] -= tp * f[i][k];
}
}
for(int i = cnt; i; --i)
{
ans[i] = f[i][cnt + 1];
for(int j = i - 1; j; --j) f[j][cnt + 1] -= f[j][i] * ans[i];
}
}
int main()
{
//MYFILE();
Mem(head, -1);
n = read(), m = read(), A = read(), B = read();
cnt = n * n;
for(int i = 1; i <= m; ++i)
{
int x = read(), y = read();
addEdge(x, y), addEdge(y, x);
}
for(int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
init(), Gauss();
for(int i = 1; i <= n; ++i) printf("%.8lf
", ans[N(i, i)]);
return 0;
}