bzoj 2337

有人说这题像游走...

关于游走的思想，他死了...

明明直接从期望dp的角度考虑更简单合理嘛

首先由于是异或运算不妨逐位考虑

对于每一位，设状态$f[i]$表示从第$i$个点到第$n$个点，这一位上是$1$的概率

那么我们按边权讨论转移：

若这条边边权为$1$：$f[i]+=\frac{1-f[to]}{deg_{i}}$

若这条边边权为$0$：$f[i]+=\frac{f[to]}{deg_{i}}$

可是本题转移是成环的，因此直接dp是行不通的

但是我们可以考虑高斯消元嘛！

上面那个表达式很显然是个方程组，高斯消元解之即可！

整理一下，就得到了：$deg_{i}f[i]+[v_{i,to}==1]f[to]-[v_{i,to}==0]f[to]=\sum_{v_{i,to}==1}1$

（其实就是整合一下上面两个表达式，移个项就出来了）

算出$f[1]$乘贡献即可

（所以这题根本不需要基于点考虑边，只需要考虑点就可以了！不用研究边的期望！）

贴代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

using namespace std;

double eps=1e-8;

struct Edge

{

    int nxt;

    int to;

    int val;

}edge[20005];

int head[105];

double inr[105];

double a[105][105];

int n,m,cnt=1;

double ans=0;

void add(int l,int r,int w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

    inr[l]++;

}

void Gauss()

{

    for(int i=1;i<=n;i++)

    {

        int temp=i;

        while(fabs(a[temp][i])<=eps)temp++;

        if(temp!=i)for(int j=i;j<=n;j++)swap(a[i][j],a[temp][j]);

        double now=a[i][i];

        for(int j=i;j<=n+1;j++)a[i][j]/=now;

        for(int j=i+1;j<=n;j++)

        {

            if(fabs(a[j][i])<=eps)continue;

            now=a[j][i];

            for(int k=i;k<=n+1;k++)a[j][k]-=now*a[i][k];

        }

    }

    for(int i=n;i>=1;i--)for(int j=i-1;j>=1;j--)a[j][n+1]-=a[i][n+1]*a[j][i];

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

        if(x!=y)add(y,x,z);

    }

    for(int k=0;k<=30;k++)

    {

        memset(a,0,sizeof(a));

        for(int i=1;i<=n-1;i++)

        {

            a[i][i]=inr[i];

            for(int j=head[i];j;j=edge[j].nxt)

            {

                int to=edge[j].to;

                if(edge[j].val&(1<<k))a[i][to]+=1.0,a[i][n+1]+=1.0;

                else a[i][to]-=1.0;

            }

        }

        a[n][n]=1;

        Gauss();

        ans+=a[1][n+1]*(1<<k);

    }

    printf("%.3lf\n",ans);

    return 0;

}

巴特西

bzoj 2337

最新文章

热门文章