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。
Source
题解
若已知每条边期望走了多少次那么就可以贪心的求出解。
设(w_i) 表示第i条边期望走多少次。
那么有(w_i = dp_u / d_u + dp_v / d_v)
dp 是这个点期望走了多少次(走出！！)。
(dp_i = display sum_{e(j , i)} dp_j / d_j)
根据这个可以得到n个方程 ， 用高斯消元消出答案即可。
注意(a[1][n+1] = -1; dp[n][n] = 任意非0)
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
const int N = 520 , M = N * N;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n , m;
int d[N] , eu[M] , ev[M];
double a[N][N] , w[M] , x[N];
void calc(int n , int m)
{
for(int i = 1 ; i < n ; ++i)
{
int res = i;
for(int j = i + 1 ; j <= n ; ++j) if(fabs(a[j][i]) > fabs(a[res][i])) res = j;
if(i != res) swap(a[i] , a[res]);
for(int j = i + 1 ; j <= n ; ++j)
{
double k = a[j][i] / a[i][i];
for(int s = i ; s <= m ; ++s) a[j][s] -= a[i][s] * k;
}
}
for(int i = m-1 ; i >= 1 ; --i)
{
for(int j = i+1 ; j < m ; ++j) a[i][m] -= a[j][j] * a[i][j];
a[i][i] = a[i][m] / a[i][i];
}
for(int i = 1 ; i <= n ; ++i) x[i] = a[i][i];
return ;
}
int main()
{
n = read(); m = read();
for(int i = 1 ; i <= m ; ++i) eu[i] = read() , ev[i] = read() , d[ev[i]]++ , d[eu[i]]++;
for(int i = 1 ; i <= m ; ++i)
{
a[eu[i]][ev[i]] += 1.0 / d[ev[i]];
a[ev[i]][eu[i]] += 1.0 / d[eu[i]];
}
for(int i = 1 ; i < n ; ++i) a[i][i] = -1 , a[n][i] = 0; a[n][n] = 1; a[1][n+1] = -1;
calc(n , n + 1);
for(int i = 1 ; i <= m ; ++i) w[i] = x[eu[i]] / d[eu[i]] + x[ev[i]] / d[ev[i]];
sort(w + 1 , w + 1 + m);
double ans = 0;
for(int i = 1 ; i <= m ; ++i) ans += i * w[m-i+1];
printf("%.3f
" , ans);
return 0;
}