[cf113d]Museum

传送门

Solution

设一个状态为 \((x,y)\) 表示两人在的位置，求出每个状态期望出现的次数

设一个状态为 \(u\) , \(x_u^0=[u==(a,b)]\)

所以一个状态出现的次数期望为 \(E_u=x_u^0+\sum_vG(v,u)\times E_v\)

其中\(G\)是状态转移的概率矩阵

高消即可，复杂度 \(O(n^6)\)

Code

#include<bits/stdc++.h>

#define ll long long

#define db double

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

const int MN=23;bool A[MN][MN];

int I[MN][MN],N,M,a,b,deg[MN];

db B[MN*MN][MN*MN],F[MN*MN],P[MN];

void Gauss(int n)

{

    reg int i,j,k;

    for(i=1;i<=n;++i)

    {

        int p=i;

        for(j=i+1;j<=n;++j)if(fabs(B[j][i])>fabs(B[p][i]))p=j;

        if(i!=p)swap(B[i],B[p]);

        for(j=i+1;j<=n;++j)

        {

            db d=B[j][i]/B[i][i];

            for(k=i;k<=n+1;++k) B[j][k]-=d*B[i][k];

        }

	}

    for(i=n;i;--i)

    {

        for(j=i+1;j<=n;++j)B[i][n+1]-=F[j]*B[i][j];

        F[i]=B[i][n+1]/B[i][i];

    }

}

db _(int x,int y){if(!A[x][y])return 0;if(x==y)return P[x];return (1.-P[x])/deg[x];}

int main()

{

	reg int i,j,x,y;

	N=read(),M=read();a=read(),b=read();

	for(i=1;i<=M;++i) x=read(),y=read(),++deg[x],++deg[y],A[x][y]=A[y][x]=1;

	for(i=1;i<=N;++i) A[i][i]=1,scanf("%lf",&P[i]);

	for(i=1;i<=N;++i)for(j=1;j<=N;++j)I[i][j]=(i-1)*N+j;

	B[I[a][b]][N*N+1]=-1.;

	for(i=1;i<=N;++i)for(j=1;j<=N;++j)

	{

		B[I[i][j]][I[i][j]]+=-1.;

		if(i!=j)for(x=1;x<=N;++x)for(y=1;y<=N;++y) B[I[x][y]][I[i][j]]+=_(i,x)*_(j,y);

	}

	Gauss(N*N);

	for(i=1;i<=N;++i) printf("%.10lf ",F[I[i][i]]);

	return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

[cf113d]Museum

传送门

Solution

Code

最新文章

热门文章