A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2337 XOR和路径 概率dp
发表于: | 分类: Oi | 评论:0 | 阅读:141

给出一张带权无向连通图,从1号节点出发,每次随机的在相邻边中选择一条走过去,走到n停止,路径的权值为路径上所有边权的异或和,问走出路径的期望权值是多少。

首先异或这个东西显然是按位算比较好
其次这个东西显然算起来与奇数和偶数有关
我们用 $f_i$ 表示从 $i$ 到达 $n$ 最后值为奇数的期望,然后分两种情况讨论

第一种边权这位是0,即有$f_i += \frac{f_j}{deg_j}$
第二种边权这位是1,即有$f_i += \frac{1-f_j}{deg_j}$
注意重边的时候,他说的是等概率的经过一条边,所以你的$deg$只需要更新一次。

然后还是老套路,把所有的式子写在一起,其中 $f_n = 0$ 是单独的一个式子
然后高斯消元,每一位加上对应的权值就行了

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 200+5;
const int M = 20000+5;
const double eps = 1e-13;
typedef long double ld;
using namespace std;

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int head[N];
int deg[N],n,m;

struct graph
{
    int next,to,val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

inline void add(int x,int y,int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z);
    head[x] = cnt; deg[x] ++;
}

ld a[N][N];

void solve()
{
    for(int i=1;i<=n;++i)
    {
        int tt = i;
        for(int j=i;j<=n;++j)
            if(fabs(a[j][i]) > eps) tt = j;
        for(int j=1;j<=n+1;++j)
            swap(a[i][j],a[tt][j]);
        for(int j=1;j<=n;++j)
            if(fabs(a[j][i]) > eps && j != i)
            {
                ld t = a[j][i] / a[i][i];
                for(int k=1;k<=n+1;++k)
                    a[j][k] -= a[i][k]*t;
            }
    }
}

int main()
{
    n = read(), m = read();
    for(int i=1;i<=m;++i)
    {
        int x = read(), y = read(), z = read();
        if(x!=y)
        {
            add(x,y,z);
            add(y,x,z);
        }
        else
            add(x,y,z);
    }

    ld ans = 0.0;
    for(int i=0;i<=30;++i)
    {
        memset(a,0,sizeof a);
        for(int x=1;x<n;++x)
        {
            a[x][x] = 1.0;
            for(int j=head[x];j;j=edge[j].next)
                if((edge[j].val)&(1<<i))
                    a[x][edge[j].to] += 1.0/deg[x],a[x][n+1] += 1.0/deg[x];
                else
                    a[x][edge[j].to] -= 1.0/deg[x];
        }
        a[n][n] = 1.0;
        solve();
        ans += (a[1][n+1]/a[1][1]) * (1<<i);
    }
    printf("%.3lf\n",(double)(ans));
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP