BZOJ 3640 JC的小苹果（逆矩阵）

浏览数：41 / 时间：2015年06月11日

题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3640

题意：给出一个无向图，从1走到n。开始是血量H，从u到达v时血量减少a[v]。每次走每条路径的概率相等。求走到n且血量大于0的概率。

思路:设f[h][u]表示到达u血量为h的概率。由于有的点到达时不掉血，这个不好弄。列出方程组，求出每个不掉血的点由哪些点到达以及他们的系数。比如x,y,z可到达r，r点不掉血，那么f[h][r]=p1*f[h][x]+p2*f[h][y]+p3*f[h][z]。这个p1、p2、p3就是r的系数。求逆矩阵可以得到。

const int N=155;
 
int n,m,K,B[N],A[N];
double x[N][N],num[N][N],f[11111][N];
int a[N][N];
 
 
void Gauss()
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++) if(fabs(x[j][i])>1e-10) break;
        if(j!=i)
        {
            for(k=1;k<=n;k++)
            {
                swap(x[i][k],x[j][k]);
                swap(num[i][k],num[j][k]);
            }
        }
        double tmp=x[i][i];
        for(k=1;k<=n;k++) x[i][k]/=tmp,num[i][k]/=tmp;
        for(j=1;j<=n;j++) if(j!=i)
        {
            tmp=x[j][i];
            for(k=1;k<=n;k++) x[j][k]-=x[i][k]*tmp,num[j][k]-=num[i][k]*tmp;
        }
    }
}
int main()
{
   
    scanf("%d%d%d",&n,&m,&K);
    int i,j,k;
    for(i=1;i<=n;i++) scanf("%d",&A[i]);
    for(i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        B[x]++;
        a[x][y]++;
        if(x!=y)
        {
            B[y]++;
            a[y][x]++;
        }
    }
    for(i=1;i<n;i++) for(j=1;j<=n;j++) if(!A[j]) x[j][i]-=1.0*a[i][j]/B[i];
    for(i=1;i<=n;i++) x[i][i]+=1,num[i][i]=1;         
    Gauss();     
    f[K][1]=1; 
    double ans=0;
    for(k=K;k>=1;k--)
    {
        for(i=1;i<n;i++) for(j=1;j<=n;j++) if(A[j]&&k+A[j]<=K&&B[i])
        {
            f[k][j]+=f[k+A[j]][i]*a[i][j]/(B[i]);
        }
        double cs[N];
        for(i=1;i<=n;i++) cs[i]=f[k][i];
        for(i=1;i<=n;i++) if(!A[i])
        {
            f[k][i]=0;
            for(j=1;j<=n;j++) if(A[j]||j==1)f[k][i]+=num[i][j]*cs[j];
        }
        ans+=f[k][n];
    }
    printf("%.8lf\n",ans);
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

BZOJ 3640 JC的小苹果（逆矩阵）