主题

主题

 
   

3143: [Hnoi2013]游走

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3143

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。


个人解法:

先不考虑1和n。

那么假设当前点x走到的概率是p[x],那么有p[x]=sigma(p[y]/Out[y]),其中(x,y)有边,Out[y]为y的度。

然后走到一条边的概率是p[x]/Out[x]+p[y]/Out[y]。可以想象在得到p之后,把图变为一个以1为中心的树(菊花图),选择(1,x)的概率是p[x]。

设计边界,对于1与n:

首先1是起点,但并不等于p[1]=1,事实上可以从别的点再次走到1,所以如果把1纳入一起计算的话(同样用p[x]=sigma(p[y]/Out[y])),应该有p[1]=sigma(p[y]/Out[y])+1。

n只会走一次,不会对任何点的概率造成贡献,p[n]也不会对边的概率造成贡献。我们可以把p[n]视为0,或者干脆不把n纳入到高斯消元中。

然后接线性方程组即可。


代码如下:
https://code.csdn.net/snippets/2258883

 
 
评论