Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom12月前

12/24
22:51
期望动规 线性代数

[bzoj 3143] [Hnoi2013]游走

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行是正整数N和M,分别表示该图的顶点数 和边数,接下来M行每行是整数u,v(1≤u,v≤N),表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N≤10,100%的数据满足2≤N≤500且是一个无向简单连通图。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

仅包含一个实数,表示最小的期望值,保留3位小数。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3 3
2 3
1 2
1 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3.333

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

边(1,2)编号为1,边(1,3)编号2,边(2,3)编号为3。

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

设a[i]为过程中经过i的期望次数,高斯消元一下

对于一条边(x,y),经过它的期望次数就是a[x]/d[x]+a[y]/d[y](f[n]=0)

期望次数多的编号小就可以了

 

[bzoj 3143] [Hnoi2013]游走