[BZOJ2337/Luogu3211][HNOI2011]XOR和路径(高斯消元)

发布于 29 天前  48 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2337/Luogu3211][HNOI2011]XOR和路径(高斯消元)

Description

给定一个无向连通图,其节点编号为 1 到 N,其边的权值为非负整数。试求出一条从 1 号节点到 N 号节点的路径,使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边,当一条边在路径中出现多次时,其权值在计算“XOR 和”时也要被重复计算相应多的次数。
直接求解上述问题比较困难,于是你决定使用非完美算法。具体来说,从 1 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 N 号节点为止,便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

Tag

高斯消元

解决思路

$XOR$不能直接消元计算,那么就分开每一位来算。
对于每一位,设$F[i]$表示$i$到$n$的路径异或和为$1$的概率,则有(其中$i-u$权为$0$,$i-v$权为$1$)
$$F[i]=\sum \frac{F[u]}{Degree[i]}+\sum \frac{1-F[v]}{Degree[i]}$$
另外,由于到达$n$后就停止行动,所以有$F[n]=0$。
这样就可以得到$n$个方程,大力消元就好。
最后把答案统计起来,设当前层为$bit$,则$Ans+=F[1]*2^{bit}$-

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=110;
const int maxM=10100*2;
const ld eps=1e-6;
const int inf=2147483647;

int n,m;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM],W[maxM];
ld Degree[maxN],Mat[maxN][maxN];

void Add_Edge(int u,int v,int w);

int main()
{
    mem(Head,-1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        Add_Edge(u,v,w);
        if (u!=v) Add_Edge(v,u,w);
    }
    ld Ans=0;
    for (int bit=0;bit<31;bit++)
    {
        mem(Mat,0);
        for (int i=1;i<n;i++)
        {
            Mat[i][i]=1;
            for (int j=Head[i];j!=-1;j=Next[j])
                {
                    if ((W[j]&(1<<bit))!=0) Mat[i][V[j]]+=1.0/Degree[i],Mat[i][n+1]+=1.0/Degree[i];
                    else Mat[i][V[j]]-=1.0/Degree[i];
                }
        }
        Mat[n][n]=1;

        for (int i=1;i<=n;i++)
        {
            int j=i;
            while (fabs(Mat[j][i])<eps) j++;
            if (i!=j) for (int k=1;k<=n+1;k++) swap(Mat[j][k],Mat[i][k]);
            ld d=(ld)1.0/Mat[i][i];
            for (int k=1;k<=n+1;k++) Mat[i][k]*=d;
            for (int k=1;k<=n;k++)
                if ((k!=i)&&(fabs(Mat[k][i])>0))
                {
                    d=Mat[k][i]/Mat[i][i];
                    for (int l=1;l<=n+1;l++) Mat[k][l]=Mat[k][l]-Mat[i][l]*d;
                }
        }

        Ans=Ans+Mat[1][n+1]*(ld)(1ll<<bit);
    }
    printf("%.3LF\n",Ans);
    return 0;
}

void Add_Edge(int u,int v,int w)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
    Degree[u]+=1.0;
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2337/Luogu3211][HNOI2011]XOR和路径(高斯消元)


HNCJ OIer 一枚