[BZOJ1778/Luogu2973][Usaco2010 Hol]Dotp 驱逐猪猡(高斯消元,期望)

发布于 2018-03-27  84 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1778/Luogu2973][Usaco2010 Hol]Dotp 驱逐猪猡(高斯消元,期望)

Description

奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡。猪猡的文明包含1到N (2 <= N <= 300)一共N个猪城。这些城市由M (1 <= M <= 44,850)条由两个不同端点A_j和B_j (1 <= A_j<= N; 1 <= B_j <= N)表示的双向道路连接。保证城市1至少连接一个其它的城市。一开始臭气弹会被放在城市1。每个小时(包括第一个小时),它有P/Q (1 <= P <=1,000,000; 1 <= Q <= 1,000,000)的概率污染它所在的城市。如果这个小时内它没有污染它所在的城市,那麽它随机地选择一条道路,在这个小时内沿着这条道路走到一个新的城市。可以离开这个城市的所有道路被选择的概率均等。因为这个臭气弹的随机的性质,奶牛们很困惑哪个城市最有可能被污染。给定一个猪猡文明的地图和臭气弹在每个小时内爆炸的概率。计算每个城市最终被污染的概率。如下例,假设这个猪猡文明有两个连接在一起的城市。臭气炸弹从城市1出发,每到一个城市,它都有1/2的概率爆炸。 1--2 可知下面这些路径是炸弹可能经过的路径(最后一个城市是臭气弹爆炸的城市): 1: 1 2: 1-2 3: 1-2-1 4: 1-2-1-2 5: 1-2-1-2-1 ... 要得到炸弹在城市1终止的概率,我们可以把上面的第1,第3,第5……条路径的概率加起来,(也就是上表奇数编号的路径)。上表中第k条路径的概率正好是(1/2)^k,也就是必须在前k-1个回合离开所在城市(每次的概率为1 - 1/2 = 1/2)并且留在最后一个城市(概率为1/2)。所以在城市1结束的概率可以表示为1/2 + (1/2)^3 + (1/2)^5 + ...。当我们无限地计算把这些项一个个加起来,我们最后会恰好得到2/3,也就是我们要求的概率,大约是0.666666667。这意味着最终停留在城市2的概率为1/3,大约为0.333333333。

Tag

高斯消元,期望

题目大意

一个从一号点出发的炸弹,在每一个点有p/q的概率爆炸,否则随机选择一条出边移动。求在每一个点爆炸的概率。

解决思路

由全期望公式,设F[u]表示在第u个点爆炸的概率,那么对于与u相连的一个点v,有
\[F[u]=F[v]*(1-\frac{p}{q})*(v到u的路径条数)/(点v的度数)+[u是否是1号点]\]
由于F的转移顺序是不确定的,所以我们可以转化为n个n元一次方程组,高斯消元得到每一个F[i]。
由于对于每一个点的\(\frac{p}{q}\)都是一定的,那么记\(sum=\sum F[i]\),在第i个点爆炸的概率就是\(\frac{F[i]}{sum}\)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=310;
const ld eps=1e-13;
const int inf=2147483647;

int n,m,P,Q;
ld F[maxN][maxN];
int Cnt[maxN][maxN],Degree[maxN];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>P>>Q;
    ld gl=(ld)1-(ld)P/(ld)Q;
    for (int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        Cnt[u][v]++;Cnt[v][u]++;//统计路径条数
        Degree[u]++;Degree[v]++;//统计度数
    }
    F[1][n+1]=-1;
    for (int i=1;i<=n;i++)//构造转移矩阵
    {
        F[i][i]=-1;
        for (int j=1;j<=n;j++)
            if (Cnt[j][i])
                F[i][j]+=(ld)gl*(ld)Cnt[j][i]/(ld)Degree[j];
    }

    int now=0;
    for (int i=1;i<=n;i++)//高斯消元
    {
        int j=i;
        while (fabs(F[j][i])<eps) j++;
        for (int k=1;k<=n+1;k++) swap(F[i][k],F[j][k]);
        ld d=(ld)1/F[i][i];
        for (int k=1;k<=n+1;k++) F[i][k]*=d;
        for (int k=1;k<=n;k++)
            if ((k!=i)&&(fabs(F[k][i])>eps))
            {
                d=F[k][i]/F[i][i];
                for (int l=1;l<=n+1;l++) F[k][l]=F[k][l]-F[i][l]*d;
            }
    }
    ld sum=0;//所有出现概率之和
    for (int i=1;i<=n;i++) sum+=F[i][n+1];
    for (int i=1;i<=n;i++) printf("%.9LF\n",fabs(F[i][n+1]/sum));
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1778/Luogu2973][Usaco2010 Hol]Dotp 驱逐猪猡(高斯消元,期望)


HNCJ OIer