前置知识：高斯消元
已知 \(n\) 元线性一次方程组。关于 \(x_1,x_2,\cdots,x_n\)。
\[\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases} \]求出它的唯一解。或者无解。或者无数解。
考虑写成一个类似矩阵的形式（假设 \(n=3\)）：
\[\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} &|& b_1\\ a_{2,1} & a_{2,2} & a_{2,3} &|& b_2\\ a_{3,1} & a_{3,2} & a_{3,3} &|& b_3 \end{bmatrix}\]对于这个矩阵我们可以有三种操作，而不改变它的任何信息：
- 交换任意两行。
- 对于一行的所有数字乘上同一个不为零的数。
- 将某一行与另一行对应位置相加，放在另一行，前面的某一行不变。
我们可以用这三种操作解这个矩阵，如果有解。我们的做法是这样的：
- 选一行的一个未知数。
- 化其为一。
- 用它消掉其他行的这个未知数，这样这个矩阵就只剩下它一个了。
- 重复上述操作 \(n\) 次以至于每一行都形如 \(x_i=b'_i\)。
没有唯一解的情况，就是找完所有行发现有一个未知数完全没有了。
细分无解和无数解请见 https://www.luogu.com.cn/problem/solution/P2455 我不想再写了
problem
\(n\) 个点 \(m\) 条边的无向简单图。每条边应该有一个权值，你要用 \(1\) 到 \(m\) 的数字给它们赋权值，一个数字只能用一次。
一个人在图上，从 1 开始随机游走，每次等概率选择一条边走过去，花费代价是这条边的权值。
请合理地赋权值，使得这个人第一次走到 \(n\) 的期望代价最小。\(n\leq 500\)。
solution 1（\(n\leq 10\)）
假设 \(E[i]\) 为从 \(i\) 第一次走到 \(n\) 的期望代价，可以写成一个关于其他 \(E[j]\) 和边权的多项式。
通过将 \(E[i]\) 当作未知数高斯消元，得到表示 \(E[1]\) 的关于所有边权的多项式。将这个多项式的系数从小到大排序，系数更小的赋予更大的权值，这样就能使 \(E[1]\) 最小。
solution 2
solution 1 的劣势在于边数太多了（\(O(n^2)\)），无法高斯消元。
考虑我们最后算出来那个系数是什么，实际上是那一条边的期望经过次数。而注意到 \((u,v)\) 边的经过次数显然等于 \(\frac{f_u}{deg_u}+\frac{f_v}{deg_v}\)，其中 \(f_i\) 表示这个点的期望经过次数。
考虑计算 \(f_i\)。
- \(f_n=0\)。
- \(f_i=\sum_v\frac{f_v}{deg_v}\)
- 注意 \(f_1\) 一上来就要经过一次，所以是 \(f_1=1+\sum_v\frac{f_v}{deg_v}\)
高斯消元上述内容即可。
code
点击查看代码
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const double eps=1e-7;
int n,m,deg[510],U[1<<18],V[1<<18];
vector<double> a[510];
void guass(){
auto dec=[&](int i,int j,double d){for(int k=0;k<=n;k++) a[i][k]-=a[j][k]*d;};
auto div=[&](int i,double d){for(int k=0;k<=n;k++) a[i][k]/=d;};
for(int i=0;i<n;i++){
int r=i;
for(int j=i+1;j<n;j++) if(fabs(a[j][i])>fabs(a[r][i])) r=j;
if(fabs(a[r][i])<eps) assert(0);
swap(a[i],a[r]);
for(int j=0;j<n;j++) if(i!=j) dec(j,i,a[j][i]/a[i][i]);
}
for(int i=0;i<n;i++) div(i,a[i][i]);
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&U[i],&V[i]),deg[--U[i]]++,deg[--V[i]]++;
for(int i=0;i<n;i++) a[i]=vector<double>(n+1),a[i][i]=-1;
for(int i=1;i<=m;i++){
auto add=[&](int u,int v){if(u!=n-1) a[u][v]+=1.0/deg[v];};
add(U[i],V[i]),add(V[i],U[i]);
}
a[0][n]=-1,a[n-1][n-1]=1;
guass();
vector<double> w; w.reserve(m);
for(int i=1;i<=m;i++) w.push_back(a[U[i]][n]/deg[U[i]]+a[V[i]][n]/deg[V[i]]);
sort(w.begin(),w.end());
double ans=0;
for(int i=0;i<m;i++) ans+=w[i]*(m-i);
printf("%.10lf\n",ans);
return 0;
}