【BZOJ】概率与期望4题

2015.08.10 10:45 Mon | 40次阅读 | 旧日oi | 固定链接 | 源码

3036:绿豆蛙的归宿

给出一个有向无环的连通图,起点为1终点为N,每条边都有一个长度。绿豆蛙从起点出发,走向终点。
到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?
很基础的一道题,令f[i]表示i到n期望的路径数,则f[i]=sigma(f[v])/out[i],v是从i能到达的点,因为是拓扑图,所以不需要判环。
这题正着做倒着做都有些问题,然而倒着做过了……
算了反正大概就是这么回事

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define N 100005
int n,m;
struct edge{
    int to,next,val;
}e[N<<1];
int h[N],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
double f[N];
int ind[N],in[N];
queue<int> q;
int main()
{
    cin>>n>>m;
    for(int a,b,c,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        ae(b,a,c);ind[a]++,in[a]++;
    }
    q.push(n);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        if(in[u]) f[u]/=in[u];
        for(int i=h[u];e[i].to;i=e[i].next)
        {
            f[e[i].to]+=f[u]+e[i].val;
            ind[e[i].to]--;
            if(!ind[e[i].to]) q.push(e[i].to);
        }
    }
    printf("%.2lf\n",f[1]);
}

## 4204: 取球游戏
M个球,一开始每个球均有一个初始标号,标号范围为1N且为整数,标号为i的球有ai个,并保证Σai = M
每次操作等概率取出一个球(即取出每个球的概率均为1/M),若这个球标号为kk < N),则将它重新标号为k + 1;若这个球标号为N,则将其重标号为1。(取出球后并不将其丢弃)
现在你需要求出,经过K次这样的操作后,每个标号的球的期望个数。
f[i][j]表示i轮后编号为j的球的期望个数。
f[i][j]=f[i-1][j]+1/m*f[i-1][j-1]-1/m*f[i-1][j]
然后矩阵乘法可以把复杂度降到n^3logk
然后发现矩阵是循环矩阵,所以可以把n^3降到n^2,具体方法我就不说了。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,k;
double a[1005],mul[1005],ret[1005],c[1005];
void mmul(double a[],double b[])
{
    for(int i=1;i<=n;i++)
    {
        c[i]=0;
        for(int j=1;j<=n;j++)
        c[i]+=a[j]*b[(i-j+n)%n+1];
    }
    for(int i=1;i<=n;i++) a[i]=c[i];
}
void mpow(int k)
{
    while(k)
    {
        if(k&1) mmul(ret,mul);
        k>>=1;mmul(mul,mul);
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);    
    mul[1]=(m-1)*1.0/m;mul[2]=1.0/m;ret[1]=1;
    mpow(k);mmul(a,ret);
    for(int i=1;i<=n;i++) printf("%.3lf\n",a[i]);
}

## 2510: 弱题
4204

## 2878: [Noi2012]迷失游乐园
首先考虑树上的情况
sum[i]表示i点向下走的期望长度,up[i]表示向上走的期望步数。这个dfs两遍就可以求出来,然后树上的问题我们就解决了。
然后看环,我们只需要处理出环上节点的up值就可以了,这个可以对每个点再dfs一遍搞定。其它的处理和树上一样。
这题麻烦的主要是实现……看代码吧,5dfs……
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
struct edge
{
    int to,next,val;
}e[N<<1];
int h[N],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
int n,m;
double sum[N],up[N],ex[N],ans;
int siz[N];
int cir[N],dep[N],fa[N],cnt;
bool vis[N];
void dfs1(int u,int f)
{
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f&&!vis[e[i].to])
    {
        siz[u]++;dfs1(v,u);sum[u]+=e[i].val;
        if(siz[v]) sum[u]+=sum[v]/siz[v];
    }
}
void dfs2(int u,int f,int d=0)
{
    if(f)
    {
        if(f==1&&siz[f]==1) up[u]=d;
        else if(siz[u]) up[u]=d+(up[f]+sum[f]-sum[u]/siz[u]-d)/(siz[f]-(f==1));
        else up[u]=d+(up[f]+sum[f]-d)/(siz[f]-(f==1));
    }
    for(int i=h[u];e[i].to;i=e[i].next)
    if(e[i].to!=f) dfs2(e[i].to,u,e[i].val);
}
void dfs3(int u,int f,int d)
{
    dep[u]=d;fa[u]=f;
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f)
    {
        if(dep[v]&&!cnt)
        {
            cir[++cnt]=u;
            cir[++cnt]=v;
            vis[u]=vis[v]=1;
            while(u!=v)
            {
                if(dep[v]<dep[u]) u=fa[u],cir[++cnt]=u,vis[u]=1;
                else v=fa[v],cir[++cnt]=v,vis[v]=1;
            }
        }
        else if(!dep[v]) dfs3(v,u,d+1);
    }
}
void dfs4(int u,int f,int d=0)
{
    if(f)
    {
        if(siz[u]) up[u]=d+(up[f]+sum[f]-sum[u]/siz[u]-d)/(siz[f]+vis[f]);
        else up[u]=d+(up[f]+sum[f]-d)/(siz[f]+vis[f]);
    }
    for(int i=h[u];e[i].to;i=e[i].next)
    if(e[i].to!=f&&!vis[e[i].to]) dfs4(e[i].to,u,e[i].val);
}
double dfs5(int tp,int u,int f)
{
    double tmp=0;
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f&&vis[v])
    {
        if(v==tp) tmp+=siz[u]?sum[u]/siz[u]:0;
        else if(u!=tp) tmp+=(e[i].val+dfs5(tp,v,u)+sum[u])/(siz[u]+1);
        else tmp+=e[i].val+dfs5(tp,v,u);
    }
    return tmp;
}
int main()
{
    cin>>n>>m;
    for(int u,v,w,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);ae(v,u,w);
    }
    if(m==n-1)
    {
        dfs1(1,0);dfs2(1,0);
        for(int i=1;i<=n;i++)
        {
            ex[i]=(sum[i]+up[i])/(siz[i]+(i!=1));
            ans+=ex[i];
        }
        printf("%.5lf\n",ans/n);
    }
    else
    {
        dfs3(1,0,1);
        for(int i=1;i<cnt;i++)
        dfs1(cir[i],0);
        for(int i=1;i<cnt;i++)
        up[cir[i]]=dfs5(cir[i],cir[i],0);
        for(int i=1;i<cnt;i++)
        dfs4(cir[i],0);
        for(int i=1;i<=n;i++)
        {
            ex[i]=(sum[i]+up[i])/(siz[i]+1+vis[i]);
            ans+=ex[i];
        }
        printf("%.5lf\n",ans/n);
    }
}```