Description：一个无向连通图，顶点从1编号到N，边从1编号到M。 小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
2≤N≤500
要用高斯消元做。
定义f[i]为期望的到点i的次数，du[i]为点i的度数。那么有
注意点n只进不出，所以它对其他点的到达次数没有贡献。
点1一开始就有一次到达。
我们现在有了n个n元一次方程。由于这个方程不规则，所以我们只能用数值解法来解这个方程。这里采用高斯消元法。
把f解出来后，就把走每条边的期望次数g[e]求出来。
然后从大到小排个序，从1到m标号即可。
代码：
#include <cstdio>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
#define MAXN 511
#define MAXM 250011
typedef pair<int, int> pii;
const double eps = 1e-8;
struct GRAPH {
vector<vector<int> > s;
void ClearEdges() {
for (auto& i : s) {
i.resize(0);
}
}
void Init(int n) {
ClearEdges();
s.resize(n + 1);
}
void AddUndi(int u, int v) {
s[u].push_back(v);
s[v].push_back(u);
}
};
struct MATRIX {
vector<vector<double> > s;
MATRIX() {}
MATRIX(size_t a, size_t b) {
resize(a, b);
}
inline size_t row() const {
return s.size();
}
inline size_t col() const {
return s.at(0).size();
}
void resize(size_t a, size_t b) {
s.resize(a);
for (size_t i = 0; i < a; ++i)
s[i].resize(b);
}
void clear() {
for (auto& i : s)
for (auto& j : i)
j = 0;
}
void swap_row(size_t i, size_t j, size_t k = 0) {
for (; k < col(); ++k)
swap(s[i][k], s[j][k]);
}
//s[i] -= s[j] * d
void sub_row(size_t i, size_t j, double d, size_t k = 0) {
for (; k < col(); ++k)
s[i][k] -= d * s[j][k];
}
//O(n^3)
void ToUpper(MATRIX& b) {
for (size_t i = 0; i < row(); ++i) {
double maxv = fabs(s[i][i]);
size_t mr = i;
for (size_t j = i + 1; j < row(); ++j) {
if (maxv < fabs(s[j][i])) {
maxv = fabs(s[j][i]);
mr = j;
}
}
swap_row(i, mr, i);
b.swap_row(i, mr);
if (maxv < eps) continue;
for (size_t j = i + 1; j < row(); ++j) {
double d = s[j][i] / s[i][i];
sub_row(j, i, d, i);
b.sub_row(j, i, d);
}
}
}
};
//ax = b
MATRIX solve_destory(MATRIX& a, MATRIX& b) {
a.ToUpper(b);
for (int i = a.row() - 1; i; --i) {
assert(fabs(a.s[i][i]) > eps);
b.s[i][0] /= a.s[i][i];
for (int j = 0; j < i; ++j) {
b.s[j][0] -= b.s[i][0] * a.s[j][i];
}
}
return b;
}
int main() {
GRAPH g;
static pii es[MAXM];
static double gs[MAXN];
int n, m;
scanf("%d%d", &n, &m);
g.Init(n);
for (int i = 0; i < m; ++i) {
scanf("%d%d", &es[i].first, &es[i].second);
--es[i].first;
--es[i].second;
}
for (int i = 0; i < m; ++i) {
g.AddUndi(es[i].first, es[i].second);
}
MATRIX b(n, 1);
b.clear();
b.s[0][0] = 1;
MATRIX a(n, n);
for (int i = 0; i < n; ++i) {
a.s[i][i] = 1;
for (int v : g.s[i]) {
if (v != n-1)
a.s[i][v] = -1.0 / g.s[v].size();
}
}
b = solve_destory(a, b);
b.s[n-1][0] = 0;
for (int i = 0; i < m; ++i) {
gs[i] = b.s[es[i].first][0] / g.s[es[i].first].size() + b.s[es[i].second][0] / g.s[es[i].second].size();
}
sort(gs, gs + m, greater<double>());
double ans = 0;
for (int i = 0; i < m; ++i) {
ans += gs[i] * (i + 1);
}
printf("%.3f\n", ans);
return 0;
}