P3211 [HNOI2011] XOR和路径

题目描述

给定一个无向连通图，其节点编号为 $1$ 到 $N$，其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算“XOR 和”时也要被重复计算相应多的次数。

直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 $1$ 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 $N$ 号节点为止，便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

数据范围

• $30%$ 的数据满足 $N\le 30$。
• $100%$ 的数据满足 $2\le N\le 100$，$M\le 10000$，但是图中可能有重边或自环。

solution

思路参考https://www.luogu.com.cn/article/nfftx7as 。
初看这个问题是不难想到令$dp_i$代表从节点$i$到节点$n$经过路径的数学期望值，但是$XOR$不太好处理，联想到$XOR$对于每一位来说本质上是加法，故考虑分别对于每一位进行处理。
则对于第$d$位有
$$deg_x\times dp_x = \displaystyle\sum_{(z >> d & 1) == 0}^{}dp_y + \sum_{(z >> d & 1) == 1}^{}(1 - dp_y)$$ $$ans+=2^d\times dp_1$$ 高斯消元即可求解。
时间复杂度：$O(n^3)$。

code

// 思路参考https://www.luogu.com.cn/article/nfftx7as
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 110,M = 10010;
const double eps = 1e-9;
int n,m;
int ver[2 * M],edge[2 * M],nx[2 * M],head[N],tot = 0;
void add(int x,int y,int z) {
    ver[++tot] = y,edge[tot] = z,nx[tot] = head[x],head[x] = tot;
}
int deg[N];
double a[N][N],ans;
void gauss() {
    for (int i = 1; i <= n; i++) {
        int mx = i;
        for (int j = i + 1; j <= n; j++) {
            if (fabs(a[j][i]) > fabs(a[mx][i])) {
                mx = j;
            }
        }
        for (int j = n + 1; j >= i; j--) {
            a[mx][j] /= a[mx][i];
            swap(a[i][j],a[mx][j]);
        }
        for (int j = i + 1; j <= n; j++) {
            for (int k = n + 1; k >= i; k--) {
                a[j][k] -= a[i][k] * a[j][i];
            }
        }
    }
    for (int i = n; i > 1; i--) {
        for (int j = i - 1; j >= 1; j--) {
            a[j][n + 1] -= a[j][i] * a[i][n + 1];
            a[j][i] = 0;
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x,y,z;
        cin >> x >> y >> z;
        if (x == y) {
            add(x,y,z);
            deg[x]++;
        }
        else {
            add(x,y,z),add(y,x,z);
            deg[x]++,deg[y]++;
        }
    }
    for (int d = 0; d <= 30; d++) {
        memset(a,0,sizeof(a));
        for (int x = 1; x < n; x++) {
            a[x][x] -= deg[x];
            for (int i = head[x]; i; i = nx[i]) {
                int y = ver[i],z = edge[i];
                if ((z >> d) & 1) {
                    a[x][y] -= 1,a[x][n + 1] -= 1;
                }
                else {
                    a[x][y] += 1;
                }
            }
        }
        a[n][n] = 1;
        gauss();
        ans += (1 << d) * a[1][n + 1];
    }
    printf("%.3f",ans);
    system("pause");
    return 0;
}

warning

对于重边只加一遍。