c/c++语言开发共享BZOJ2337: [HNOI2011]XOR和路径(期望 高斯消元)

题意

题目链接

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 */