[HNOI2011]XOR和路径

list1 2019-03-16 原文

Description:

Hint:

100%的数据满足2≤N≤100，M≤10000

Solution:

显然是高斯消元解方程组

怎么列? 考虑按位计算,现在处理到第t位

设\(f[i]\)为走到i点这一位为1的期望

则有\(f[i]=\frac{\sum_{w(i,j)\&t==0} f[j]+\sum_{w(i,j)\&t==1} (1-f[j])} {deg[i]}\)

\(deg[i]*f[i]-\sum_{w(i,j)\&t==0} f[j] +\sum_{w(i,j)\&t==1} f[j] =\sum_{w(i,j)\&t==1} 1\)

注意第n行只有n系数为1,等式右边为0

每一位算一次再把a[1]加起来就是答案

高斯消元老是写错…

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=5005;
const double eps=1e-2;
int n,m,cnt,d[mxn*1000],p[mxn*1000],q[mxn*1000],hd[mxn*1000];
double ans,res[mxn*1000],a[mxn][mxn];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline int chkmax(int &x,int y) {if(x<y) x=y;}
inline int chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {
    int to,nxt,w;
}tt[mxn<<7];

inline void add(int u,int v,int w) {
    tt[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
}

int main()
{
    n=read(); m=read(); int u,v,w,mx=0;
    for(int i=1;i<=m;++i) {
        u=read(); v=read(); w=read();
        add(u,v,w); ++d[v]; if(u!=v) add(v,u,w),++d[u];
        chkmax(mx,w);
        p[i]=u; q[i]=v;
    }
    for(int t=1;t<=mx;t<<=1) {
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=n+1;++j) 
            a[i][j]=0.0;
    a[n][n]=1.0;
    for(int i=1;i<n;++i) {
        a[i][i]=d[i];
        for(int j=hd[i];j;j=tt[j].nxt) {
            int v=tt[j].to;
            if(!(tt[j].w&t)) a[i][v]--;
            else a[i][v]++,a[i][n+1]++;
        }
    }
    for(int i=1;i<=n;++i) {
        int now=i; double tp=a[i][i];
        for(int j=i+1;j<=n;++j) 
            if(fabs(a[j][i])-fabs(tp)>eps)
                now=j,tp=a[j][i];
        if(now!=i) 
            for(int j=1;j<=n+1;++j) swap(a[i][j],a[now][j]);
        for(int j=n+1;j>=i;--j) a[i][j]/=a[i][i];   
        for(int j=1;j<=n;++j) 
            if(i!=j&&a[j][i]) 
                for(int k=n+1;k>=i;--k) 
                    a[j][k]-=a[j][i]*a[i][k];
    }
    ans+=1.0*a[1][n+1]*(double) t;
    }
    printf("%.3lf\n",ans);
    return 0;
}