标签: 高斯消元

「HNOI2013」游走

给定一个 n 个点 m 条边的无向连通图,顶点从 1 编号到 n,边从 1 编号到 m。

小 Z 在该图上进行随机游走,初始时小 Z 在 1 号顶点,每一步小 Z 以相等的概率随机选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小 Z 到达 n 号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这 m 条边进行编号,使得小 Z 获得的总分的期望值最小。