[HNOI2011]XOR和路径(https://www.cnblogs.com/beretty/p/9540612.html)

题目描述

给定一个无向连通图，其节点编号为 1 到 N，其边的权值为非负整数。试求出一条从 1 号节点到 N 号节点的路径，使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算“XOR 和”时也要被重复计算相应多的次数。
直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 1 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 N 号节点为止，便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

输入描述:

从文件input.txt中读入数据，输入文件的第一行是用空格隔开的两个正整数N和M，分别表示该图的节点数和边数。
紧接着的M行，每行是用空格隔开的三个非负整数u，v和w(1≤u,v≤N，0≤w≤109)，表示该图的一条边(u,v)，其权值为w。
输入的数据保证图连通，30%的数据满足N≤30，100%的数据满足2≤N≤100，M≤10000，但是图中可能有重边或自环。

输出描述:

输出文件 output.txt 仅包含一个实数，表示上述算法得到的路径的“XOR 和”的期望值，要求保留三位小数。（建议使用精度较高的数据类型进行计算）

示例1

输入
2 2
1 1 2
1 2 3
输出
2.333

思路

看起来比较常规:f[i]:i到n的期望值。
\(f[u]=\sum (f[to] 异或 w)/d[u]\)
因为可以有环，递推是不可能了。当然是上高斯消元。
但是高斯消元，不能异或。位运算我们考虑拆位。
对于每一位，我们能不能把式子变成乘。我们必须把f[i]的含义改了
f[i]:f[i]:i到n第pos位为1的概率。
如果u-v的边的pos位为1。
那么f[u]=(1-f[to])/d[u]
如果u-v的边的pos位为0。
那么f[u]=(f[to])/d[u]

#include<bits/stdc++.h>
using namespace std;

const double eps=1e-8;
const int maxn=105;
double a[maxn][maxn];

void Gauss(int n) {
    for(int i=1; i<=n; ++i) {
        int r=i;
        for(int j=i+1; j<=n; ++j) //找主元系数的绝对值最大的一行
            if(fabs(a[j][i])>fabs(a[r][i]))
                r=j;
        if(fabs(a[r][i])<eps) {  //最大为0,无解
            printf("No Solution\n");
            return;
        }
        if(r!=i)
            for(int j=1; j<=n+1; ++j)
                swap(a[i][j],a[r][j]);
        for(int j=1; j<=n; ++j)  //消元
            if(j!=i) {
                double tmp=a[j][i]/a[i][i];
                for(int k=i; k<=n+1; ++k)
                    a[j][k]-=a[i][k]*tmp;
            }
    }
//    for(int i=1; i<=n; ++i)
//        printf("%.2f\n",a[i][n+1]/a[i][i]);
}

struct Edge {
    int to, w;
};
vector<Edge> G[105];

int main() {

    int n, m; scanf("%d%d",&n, &m);
    for(int i=1; i<=m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G[a].push_back({b, c});
        if(a!=b){
            G[b].push_back({a, c});
        }
    }
    double ans=0;
    for(int pos=0; pos<=31; pos++) {
        memset(a, 0, sizeof(a));
        a[n][n]=1;
        for(int u=1; u<n; u++) {
            int sz=G[u].size();
            a[u][u]=1;
            for(auto x: G[u]) {
                int to=x.to, w=x.w;
                if((w&(1<<pos))) {
                    a[u][to]+=1.0/sz;
                    a[u][n+1]+=1.0/sz;
                } else {
                    a[u][to]-=1.0/sz;
                }
            }
        }
        Gauss(n);
        ans+=(1<<pos)*a[1][n+1]/a[1][1];
    }
    printf("%.3f\n", ans);

    return 0;
}