刚学完 高斯消元，我们来做几道题吧！
T1：【BZOJ3143】【HNOI2013】游走
Description
一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 N 号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
Input
第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来MM行每行是整数u，v(1≤u,v≤N)u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。
输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。
Output
仅包含一个实数，表示最小的期望值，保留3位小数。
题解：
这明显是一道概率期望题嘛！
一条边经过的概率为 $E(u,v)={f_u \over deg_u}+{f_v \over deg_v}$ ，其中u，v为边的两个端点，fx 表示过x点的概率， degx 表示点 x的度数（出度、入度）。
一个点经过的概率为 $f_u=\sum_v f_v\times deg_v$ ， v 为与 u 相连的一个节点。
知道了这些，我们还是不能用 dp 求解，因为它不符合决策单调性，即一个点走过去还能走回来，一个点的概率会互相影响，这我们就要列方程求解了。
$$a[i][j]= 1/deg[j]$$
我们这样列一个方程组，不过要注意的是 1号点它是必定经过的所以概率要加 1，n 的概率为 0
然后我们贪心，期望大的编号小。
CODE：
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std; int n,m,u[],v[],deg[];
double a[][],g[],res; void gauss(){
for(int i=,maxn=i;i<n;maxn=++i){
for(int j=i+;j<=n;j++)
if(fabs(a[j][i])>fabs(a[maxn][i]))maxn=j;
for(int j=;j<=n+;j++)swap(a[i][j],a[maxn][j]);
for(int j=i+;j<=n;j++){
if(fabs(a[j][i])<1e-)continue;
double s=a[j][i]/a[i][i];
for(int k=;k<=n+;k++)a[j][k]-=a[i][k]*s;
}
}
for(int i=n;i>=;i--){
for(int j=i+;j<=n;j++)
a[i][n+]-=a[i][j]*a[j][n+];
a[i][n+]/=a[i][i];
}
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",u+i,v+i);
deg[u[i]]++,deg[v[i]]++;
}
a[][n+]=-,a[n][n]=;
for(int i=;i<=m;i++){
if(u[i]^n)a[u[i]][v[i]]=1.0/deg[v[i]];
if(v[i]^n)a[v[i]][u[i]]=1.0/deg[u[i]];
}
for(int i=;i<n;i++)a[i][i]=-;
gauss();
for(int i=;i<=m;i++)
g[i]=a[u[i]][n+]/deg[u[i]]+a[v[i]][n+]/deg[v[i]];
sort(g+,g+m+);
for(int i=;i<=m;i++)res+=g[i]*(m-i+);
printf("%.3f\n",res);
}
T2：【BZOJ3270】博物馆
Description
Input
Output
题解：
这回是两个人，同样 id[i][j] 表示 Petya 在 i ，Vasya 在 j 。
设 a[id[x][y]][id[i][j]] 为从状态 id[i][j] 转移到 id[x][y] 的概率来列个方程组
假设现在在 id[i][j] 这个状态上，接下来有这么几种情况
1：两个人同时停留在原点， a[id[i][j]][id[i][j]]=p[i]*p[j] ;
2：第一个人走到了x(前提是i->x有边存在)， a[id[x][j]][id[i][j]]+=(1-p[i])/du[i]*p[j] ;
3：第二个人走到了y， a[id[i][y]][id[i][j]]+=p[i]*(1-p[j])/du[j] ;
4：第一个人走到了x，第二个人走到了y， a[id[x][y]][id[i][j]]+=(1-p[i])/du[i]*(1-p[j])/du[j] ;
同上，把方程解出来即可。
CODE：
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std; int n,m,u[],v[],deg[];
double a[][],g[],res; void gauss(){
for(int i=,maxn=i;i<n;maxn=++i){
for(int j=i+;j<=n;j++)
if(fabs(a[j][i])>fabs(a[maxn][i]))maxn=j;
for(int j=;j<=n+;j++)swap(a[i][j],a[maxn][j]);
for(int j=i+;j<=n;j++){
if(fabs(a[j][i])<1e-)continue;
double s=a[j][i]/a[i][i];
for(int k=;k<=n+;k++)a[j][k]-=a[i][k]*s;
}
}
for(int i=n;i>=;i--){
for(int j=i+;j<=n;j++)
a[i][n+]-=a[i][j]*a[j][n+];
a[i][n+]/=a[i][i];
}
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",u+i,v+i);
deg[u[i]]++,deg[v[i]]++;
}
a[][n+]=-,a[n][n]=;
for(int i=;i<=m;i++){
if(u[i]^n)a[u[i]][v[i]]=1.0/deg[v[i]];
if(v[i]^n)a[v[i]][u[i]]=1.0/deg[u[i]];
}
for(int i=;i<n;i++)a[i][i]=-;
gauss();
for(int i=;i<=m;i++)
g[i]=a[u[i]][n+]/deg[u[i]]+a[v[i]][n+]/deg[v[i]];
sort(g+,g+m+);
for(int i=;i<=m;i++)res+=g[i]*(m-i+);
printf("%.3f\n",res);
}