题意
Sol
期望的线性性对xor运算是不成立的,但是我们可以每位分开算
设\(f[i]\)表示从\(i\)到\(n\)边权为1的概率,统计答案的时候乘一下权值
转移方程为
\[f[i] = (w = 1) \frac{1 - f[to]}{deg[i]} +(w = 0) \frac{f[to]}{deg[i]} \]高斯消元解一下
注意:f[n] = 0,有重边!
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1001;
inline int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, deg[MAXN];
vector<int> a[MAXN][MAXN];
double f[MAXN][MAXN];
void Gauss() {
for(int i = 1; i <= N - 1; i++) {
int mx = i;
for(int j = i + 1; j <= N; j++) if(f[j][i] > f[mx][i]) mx = j;
if(mx != i) swap(f[i], f[mx]);
for(int j = 1; j <= N; j++) {
if(i == j) continue;
double p = f[j][i] / f[i][i];
for(int k = i; k <= N + 1; k++) f[j][k] -= f[i][k] * p;
}
}
for(int i = 1; i <= N; i++) f[i][N + 1] /= f[i][i];
}
int main() {
//freopen("2.in", "r", stdin);
N = read(); M = read();
for(int i = 1; i <= M; i++) {
int x = read(), y = read(), z = read();
a[x][y].push_back(z);
deg[x]++;
if(x != y) deg[y]++, a[y][x].push_back(z);
}
double ans = 0;
for(int B = 0; B <= 31; B++) {
memset(f, 0, sizeof(f));
for(int i = 1; i <= N - 1; i++) {
f[i][i] = deg[i];
for(int j = 1; j <= N; j++) {
for(int k = 0; k < a[i][j].size(); k++) {
int w = a[i][j][k];
if(w & (1 << B)) {//
f[i][N + 1]++;
if(j != N) f[i][j]++;
} else {
if(j != N) f[i][j]--;
}
}
}
}
Gauss();
ans += (1 << B) * f[1][N + 1];
}
printf("%.3lf", ans);
return 0;
}
/*
3 3
1 2 4
1 3 5
2 3 6
*/