P3211 [HNOI2011] XOR和路径

题目描述

给定一个无向连通图，其节点编号为 $1$ 到 $N$，其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算“XOR 和”时也要被重复计算相应多的次数。

直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 $1$ 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 $N$ 号节点为止，便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

输入格式

输入文件的第一行是用空格隔开的两个正整数 $N$ 和 $M$，分别表示该图的节点数和边数。紧接着的 $M$ 行，每行是用空格隔开的三个非负整数 $u,v$ 和 $w$。$(1\le u,v\le N$，$0\le w\le {10}^9)$，表示该图的一条边 $(u,v)$，其权值为 $w$。输入的数据保证图连通。

输出格式

输出文件仅包含一个实数，表示上述算法得到的路径的“XOR 和”的期望值，要求保留三位小数。（建议使用精度较高的数据类型进行计算）

输入输出样例 #1

输入 #1

2 2
1 1 2
1 2 3

输出 #1

2.333

说明/提示

样例解释

有 ${\displaystyle \frac{1}{2}}$ 的概率直接从 $1$ 号节点走到 $2$ 号节点，该路径的“XOR和”为 $3$；有 ${\displaystyle \frac{1}{4}}$ 的概率从 $1$ 号节点走一次 $1$ 号节点的自环后走到 $2$ 号节点，该路径的“XOR 和”为 $1$；有 ${\displaystyle \frac{1}{8}}$ 的概率从 $1$ 号节点走两次 $1$ 号节点的自环后走到 $2$ 号节点，该路径的“XOR和”为 $3$…依此类推，可知“XOR和”的期望值为：${\displaystyle \frac{3}{2}}+{\displaystyle \frac{1}{4}}+{\displaystyle \frac{3}{8}}+{\displaystyle \frac{1}{16}}+{\displaystyle \frac{3}{32}}+\cdots ={\displaystyle \frac{7}{3}}$，约等于 $2.333$。

数据范围

• $30\mathrm{\%}$ 的数据满足 $N\le 30$。
• $100\mathrm{\%}$ 的数据满足 $2\le N\le 100$，$M\le 10000$，但是图中可能有重边或自环。

题解

我们对期望的性质知之甚少。我们只知道期望具有线性性，期望对于异或运算没有特殊的性质。因此我们只能分别考虑每一位，求出每一位是 1 的概率。

对每一位，设 $f(u)$ 表示从 $u$ 到 $n$ 的路径上这一位为 1 的概率，$d{g}_u$ 表示 $u$ 的出度。

那么 $1-f(u)$ 就是路径上这一位为 0 的概率。

$$\begin{gathered} \mathrm{\forall }(u,v)\in E.f(u)=\frac{1}{d{g}_u}(\sum _{w(u,v)=0}f(v)+\sum _{w(u,v)=1}(1-f[v]))\text{ \\ ⇒∀(u,v)∈E.dguf(u)=∑w(u,v)=0f(v)+∑w(u,v)=1(1−f[v]) \\ ⇒∀(u,v)∈E.dguf(u)−∑w(u,v)=0f(v)+∑w(u,v)=1f(v)=∑w(u,v)=11} \end{gathered}$$

高斯消元即可。最后答案按照期望定义计算 $ans=\sum _i{2}^i{f}_i(1)$。