Luogu P3232 [HNOI2013]游走 题解

题意

在一个无向图中,小$Z$以$1$为起点,每次以相等的概率选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小$Z$走到$N$(即终点),结束了这次游走,总得分为游走时经过的每一条边的编号之和。现在,请你对这$M$条边进行编号,使得小$Z$获得的总分的期望值最小。
输入保证:
1. $30$%的数据满足$N<=10$
2. $100$%的数据满足$2<=N<=500$且是一个无向简单连通图。

思路

首先要明白高斯消元

数学上,高斯消元法(或译:高斯消去法),是线性代数规划中的一个算法,可用来为线性方程组求解。但其算法十分复杂,不常用于加减消元法,求出矩阵的秩,以及求出可逆方阵的逆矩阵。不过,如果有过百万条等式时,这个算法会十分省时。一些极大的方程组通常会用迭代法以及花式消元来解决。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式”。高斯消元法可以用在电脑中来解决数千条等式及未知数。亦有一些方法特地用来解决一些有特别排列的系数的方程组。 ——转自百度百科

可以去过一过Luogu P3389 高斯消元的模板题
简单讲一下高斯消元。
如果有一个方程组,如:

将上面的方程转为下面的增广矩阵

接下来进行高斯消元。
首先找到一个第一列的数不为0的行(一般找第一列的数最大的行)(如果都为0就跳过当前步)
然后用它的第一列的数将下面行当前列的值化为0,变换过的初等矩阵与原矩阵等价,化为方程后依然成立
本矩阵第一列的数最大的为第三行就把第三行与第一行交换

然后下面行的当前列消去,如图

除了最后一列外,每一列都如此,最后得到上三角矩阵如图

这样我们就可以轻松求出$x1,x2,x3$了。
回归到这道题
我们设$deg_i$表示第$i$个点的度数,$f_i$表示第$i$个点期望经过次数:

由于当小$Z$到达$n$点时就停止游走了,因此不能考虑$n$点。接下来对$n−1$个$f_i$进行高斯消元求解。
设$g_i$表示第$i$条边期望经过次数:
$g_{i}=\frac{f_{u}}{d_{u}}+\frac{f_{v}}{d_{v}} \quad E_{i}=(u, v), u \neq n, v \neq n$
最后排序,贪心,因为要求期望值最小,那么就把最大的$g_i$编号标至最小,以此类推。

Code

高斯消元

游走

本文部分内容引自百度百科bennettzSiyuan

暂无评论

发送评论


				
上一篇
下一篇