M_sea

洛谷3211 [HNOI2011]XOR和路径
Luogu分析考虑按位处理每一位,那么在考虑每一位时边权只有 $0/1$ 。设 $f_u$ 表示 $u\to n$...
扫描右侧二维码阅读全文
27
2019/07

洛谷3211 [HNOI2011]XOR和路径

Luogu

分析

考虑按位处理每一位,那么在考虑每一位时边权只有 $0/1$ 。

设 $f_u$ 表示 $u\to n$ 的路径边权异或和为 $1$ 的概率,那么 $1-f_u$ 就是 $u\to n$ 的路径边权异或和为 $0$ 的概率。

容易得到

$$ \displaystyle f_u=\frac{1}{deg_u}\left(\sum_{w_{u,v}=0}f_v+\sum_{w_{u,v}=1}1-f_v\right) $$

整理后得到

$$ \displaystyle deg_uf_u-\sum_{w_{u,v}=0}f_v+\sum_{w_{u,v}=1}f_v=\sum_{w_{u,v}}1 $$

直接高斯消元即可。注意自环不能连两次,需要特判。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10,M=10000+10;

int n,m;
double a[N][N],b[N],c[N];

struct edge { int v,w,nxt; } e[M<<1];
int head[N],deg[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

inline void build(int bit) {
    for (re int i=1;i<=n;++i) {
        for (re int j=1;j<=n;++j) a[i][j]=0;
        b[i]=0;
    }
    a[n][n]=1;
    for (re int u=1;u<n;++u) {
        a[u][u]=deg[u];
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (w&(1<<bit)) ++a[u][v],++b[u];
            else --a[u][v];
        }
    }
}

inline void Gauss() {
    for (re int i=1;i<=n;++i) {
        int p=i;
        for (re int j=i+1;j<=n;++j)
            if (fabs(a[j][i])>fabs(a[p][i])) p=j;
        if (i!=p) swap(a[i],a[p]),swap(b[i],b[p]);
        for (re int j=1;j<=n;++j) {
            if (i==j) continue;
            double rate=a[j][i]/a[i][i];
            for (re int k=1;k<=n;++k) a[j][k]-=rate*a[i][k];
            b[j]-=rate*b[i];
        }
    }
    for (re int i=1;i<=n;++i) c[i]=b[i]/a[i][i];
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),++deg[u];
        if (u!=v) addEdge(v,u,w),++deg[v];
    }
    double ans=0;
    for (re int i=0;i<31;++i) {
        build(i); Gauss();
        ans+=c[1]*(1<<i);
    }
    printf("%.3lf\n",ans);
    return 0;
}
最后修改:2019 年 07 月 27 日 08 : 29 AM

发表评论