BZOJ2337: [HNOI2011]XOR和路径(期望 高斯消元)
程序员文章站
2022-05-17 14:44:42
题意 "题目链接" Sol 期望的线性性对xor运算是不成立的,但是我们可以每位分开算 设$f[i]$表示从$i$到$n$边权为1的概率,统计答案的时候乘一下权值 转移方程为 $$f[i] = (w = 1) \frac{1 f[to]}{deg[i]} +(w = 0) \frac{f[to]}{ ......
题意
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 */
下一篇: ionic4 开发企业微信应用0