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

题面传送门
按每一位考虑期望,设f(u)表示这一位u->n的期望,那么:

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

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

将度数移到左边然后高斯消元即可。

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

const int Maxn=105;

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

int main()
{
    scanf("%d%d",&N,&M);memset(A,-1,sizeof A);
    for(int i=1;i<=M;i++){
        scanf("%d%d%d",&x,&y,&c),Add(x,y,c),dg[y]++;
        if(x^y)Add(y,x,c),dg[x]++;
    }
    for(int T=0;T<31;T++){
        memset(F,0,sizeof F);memset(P,0,sizeof P),F[N][N]=1;
        for(int i=1;i<N;i++){
            F[i][i]=dg[i];
            for(int j=head[i];j;j=nxt[j]){
                if(w[j]&(1<<T))F[i][to[j]]+=1,F[i][N+1]++;
                else F[i][to[j]]-=1;
            }
        }
        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]);
            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+1;k++)F[j][k]-=gs*F[i][k];
            }
        }
        for(int i=N;i;i--){
            P[i]=F[i][N+1]/F[i][i];
            for(int j=i-1;j;j--)if(F[j][i])
                F[j][N+1]-=P[i]*F[j][i],F[j][i]=0;
        }
        Ans+=P[1]*(1<<T);
    }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>
*
*