Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

题面传送门

将题目中的边的期望转化为点的期望。E(u->v)=\frac{E(u)}{degree(u)}+\frac{E(v)}{degree(v)}

f(u)表示u被经过的期望。那么:

    \[f(u)=1+\sum_{(u,v)\in E}\frac{f(v)}{degree(v)}\ \ \ (u==1)\]

    \[f(u)=\sum_{(u,v)\in E}\frac{f(v)}{degree(v)}\ \ \ (u!=1)\]

1号点比较特殊,因为在出发时它是起点,就已经经过了一次。

n号点比较特殊,因为游走到n号点就结束了,所以转移是不可以从n点转移过来的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int Maxn=505;

double F[Maxn][Maxn],Ans,P[Maxn],gt[Maxn*Maxn];
int N,M,dg[Maxn],x,y,fr[Maxn*Maxn],tp[Maxn*Maxn];
int head[Maxn],nxt[Maxn*Maxn<<1],to[Maxn*Maxn<<1],Cnt;
#define Add(x,y) (nxt[++Cnt]=head[x],to[head[x]=Cnt]=y)

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
        scanf("%d%d",&x,&y);
        Add(x,y),dg[y]++;
        Add(y,x),dg[x]++;
        fr[i]=x,tp[i]=y;
    }
    F[1][N]=1;
    for(int i=1;i<N;i++){
        F[i][i]=1;
        for(int j=head[i];j;j=nxt[j])if(to[j]^N)F[i][to[j]]-=1.0/dg[to[j]];
    }
    for(int i=1;i<N;i++){
        if(!F[i][i])for(int j=i+1;j<=N;j++)if(F[j][i]){swap(F[i],F[j]);break;}
        for(int j=i+1;j<N;j++){
            if(!F[j][i])continue;
            double gs=F[j][i]/F[i][i];
            for(int k=i;k<=N;k++)F[j][k]-=gs*F[i][k];
        }
    }
    for(int i=N-1;i;i--){
        P[i]=F[i][N]/F[i][i];
        for(int j=i-1;j;j--)if(F[j][i])
            F[j][N]-=P[i]*F[j][i],F[j][i]=0;
    }
    for(int i=1;i<=M;i++)gt[i]=(fr[i]^N?(P[fr[i]]*(1.0/dg[fr[i]])):0)+(tp[i]^N?(P[tp[i]]*(1.0/dg[tp[i]])):0);
    sort(gt+1,gt+M+1);
    for(int i=M;i;i--)Ans+=1.0*(M-i+1)*gt[i];
    printf("%.3lf",Ans);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*