BZOJ3143 - Click Here
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之间存在一条边。 输入保证满足2≤N≤500且是一个无向简单连通图。
Output
仅包含一个实数，表示最小的期望值，保留3位小数。
Solutions
题目要求最小的期望值。考虑贪心分配边权，将小的边权分配给概率大的边。则问题转换成求经过某条边的概率。
注意到，对于一条边$(u,v)$，如果经过这条边，则只能够是$u \rightarrow v$或$v \rightarrow u$。因此边的概率问题转换为点的概率问题。
又因为点的概率等价于经过该点的期望次数，所以可设$f(i)$表示经过点$i$的期望次数。
则易得转移方程$f(i)=\sum_{(i,j) \in E, \, j \neq n} \frac{f(j)}{d_j}$，其中$d_i$表示$i$点的度数。
由于这个DP方程存在环，需要用高斯消元求解。
时间复杂度$O(n^3)$
CODE
CODE - Click Here