BZOJ2337：[HNOI2011]XOR和路径——题解

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

——————————————————————————————————————————

http://www.lydsy.com/JudgeOnline/problem.php?id=2337

2  3  6

不会期望怎么办？看题解……

参考：http://blog.****.net/PoPoQQQ/article/details/42223843

我们考虑将xor的操作分解成对每一位的操作，然后将边权拆成当前位，模拟xor操作即可。

剩下来的操作就和我的上一篇博客（BZOJ3143）基本上相同了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef double dl;
const int N=;
const int M=;
struct node{
    int to,nxt,w;
}e[M*];
int head[N],cnt,d[N];
inline void add(int u,int v,int w){
    cnt++;
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    d[u]++;
    return;
}
dl c[N][N],f[N][N],x[N],ans;
inline void Gauss(int n,int m){
    for(int i=;i<=n;i++){
    int l=i;
    for(int j=l+;j<=n;j++)
        if(fabs(f[l][i])<fabs(f[j][i]))l=j;
    if(l!=i)
        for(int j=i;j<=m;j++)
        swap(f[l][j],f[i][j]);
    for(int j=i+;j<=n;j++){
        dl temp=f[j][i]/f[i][i];
        for(int k=i;k<=m;k++)
        f[j][k]=f[j][k]-f[i][k]*temp;
    }
    }
    for(int i=n;i>=;i--){
    dl t=f[i][m];
    for(int j=n;j>i;j--)
        t-=x[j]*f[i][j];
    x[i]=t/f[i][i];
    }
    return ;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++){
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    add(u,v,w);
    if(u!=v)add(v,u,w);
    }
    for(int i=;i<=;i++){
    memset(f,,sizeof(f));
    memset(x,,sizeof(x));
    for(int u=;u<n;u++){
        for(int k=head[u];k;k=e[k].nxt){
        int v=e[k].to,w=e[k].w;
        if(w&(<<i))f[u][v]+=,f[u][n+]+=;
        else f[u][v]-=;
        }
        f[u][u]+=d[u];
    }
    for(int j=;j<=n+;j++)f[n][j]=;
    f[n][n]=;
    Gauss(n,n+);
    ans+=x[]*(<<i);
    }
    printf("%.3f\n",ans);
    return ;
}