【题解】金牌导航-高斯消元/Luogu P3232 游走

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
const int MAXN = 505;
const int MAXM = 130000;
struct edge{
	int nxt,to;
	edge(int _nxt = 0,int _to = 0){
		nxt = _nxt,to = _to;
	}
}e[2 * MAXM];
double a[MAXN][MAXN];
double ans[MAXN],res[MAXM];
int from[MAXM],to[MAXM],head[MAXN],du[MAXN];
int n,m,cnt;
void Gauss(int n){   //推荐里面写一个 n ，然后直接按模板敲就好了 
	for(int i=1; i<=n; i++){
		int mx = i;
		for(int j=i + 1; j<=n; j++){
			if(fabs(a[j][i]) > fabs(a[mx][i])){
				mx = j;
			}
		}
		if(mx != i) {
			for(int j=1; j<=n+1; j++){
				swap(a[i][j],a[mx][j]);
			}
		}
		for(int j=1; j<=n; j++){
			if(j != i){
				double tmp = a[j][i] / a[i][i];
				for(int k=i; k<=n+1; k++){
					a[j][k] -= tmp * a[i][k];
				}
			}
		}
	}
	for(int i=1; i<=n; i++){   //ans[i] 即我们最后解出来的解 
		ans[i] = a[i][n+1] / a[i][i];
	}
}
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
int main(){
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		cin>>from[i]>>to[i];
		add_edge(from[i],to[i]);
		add_edge(to[i],from[i]);
		du[from[i]]++;du[to[i]]++;
	}
	for(int i=1; i<n; i++){  //注意一点，因为到 n 就停了，所以 n 的期望等就不用算了 
 		a[i][i] = 1;  //根据我们的式子可以化出来 
		for(int j=head[i]; j; j = e[j].nxt){
			int to = e[j].to;
			if(to != n){  //注意 to != n 
				a[i][to] = -1.0/du[to];   //根据我们的式子可以化出来 
			}
		} 
	}
	a[1][n] = 1;  //根据式子可以化出来
	Gauss(n-1); 
	for(int i=1; i<=m; i++){
		if(from[i] != n){
			res[i] += ans[from[i]] / du[from[i]];   //到达这个点的期望除以度数，就是从这个点到当前点的期望 
		}
		if(to[i] != n){
			res[i] += ans[to[i]] / du[to[i]];
		}
	}
	sort(res+1,res+m+1);   //从小到大排边
	//一定要相信 STL,如果自己写一个 cmp（例如我），就会造成神奇的精度问题 
	double h = 0; 
	for(int i=1; i<=m; i++){ 
		//越大的期望的边给他越小的编号
		h += res[i] * (m - i + 1);
	}
	printf("%.3f",h);
	return 0;
}