P3211 [HNOI2011]XOR和路径

思路

看到异或，容易联想到二进制位之间是相互独立的，所以可以把问题变成每个二进制位为1的概率再乘上(1<<pos)的值

假设现在考虑到pos位，设f[i]为第i个节点期望的异或和第pos位是1的概率，有这样的转移方程

\[f[u]=\frac{1}{d[u]}\sum_{v}[w[i]_{pos}=1]?(1-f[v]):f[v]
\]

这是一个逆推的方程，所以f[n]=0，f[1]就是答案

然后这个方程互相依赖，所以上高斯消元求解即可

代码

注意有点卡精度，换成long double可AC

另外自环不能加两次

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#define double long double

using namespace std;

const double eps = 1e-9;

int n,m,u[20100],v[20100],w[20100],fir[110],nxt[20100],cnt,d[110];

double a[110][110],ans;

void addedge(int ui,int vi,int wi){

    ++cnt;

    u[cnt]=ui;

    v[cnt]=vi;

    w[cnt]=wi;

    nxt[cnt]=fir[ui];

    fir[ui]=cnt;

}

double gauss(void){

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

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

            if(fabs(a[j][i])>eps){

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

                    swap(a[i][k],a[j][k]);

                // break;

            }

        }

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

            if(i==j)

                continue;

            double rates=a[j][i]/a[i][i];

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

                a[j][k]=a[j][k]-rates*a[i][k];

        }

    }

    return a[1][n+1]/a[1][1];

}

void make(int pos){

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

    a[n][n]=1;

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

        a[i][i]+=d[i];

        for(int j=fir[i];j;j=nxt[j]){

                if((w[j]>>pos)&1){

                    a[i][v[j]]+=1;

                    a[i][n+1]+=1;

                }

                else{

                    a[i][v[j]]-=1;

                }

        }

    }

    double mid=gauss();

    // printf("mid=%lf\n",mid);

    ans=(ans+(1<<pos)*mid);

}

int main(){

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

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

        int a,b,c;

        scanf("%d %d %d",&a,&b,&c);

        addedge(a,b,c),d[a]++;

        if(a!=b)

            addedge(b,a,c),d[b]++;

    }

    for(int i=0;i<32;i++){

        make(i);

    }

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

    return 0;

}

巴特西

P3211 [HNOI2011]XOR和路径

思路

代码

最新文章

热门文章