欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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