[HNOI2013]游走
题目描述
一个无向连通图，顶点从1编号到N，边从1编号到M。 小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
输入输出格式
输入格式：
第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1<=u,v<=N)，表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N<=10，100%的数据满足2<=N<=500且是一个无向简单连通图。
输出格式：
仅包含一个实数，表示最小的期望值，保留3位小数。
输入输出样例
说明
边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。
我们发现每条边对答案的贡献就是走这条边的期望(Σ次数*概率)*这条边的编号。
最优方案显然是求出所有期望之后大的期望对应小的编号。。。
但是怎么求边的期望呢？？？
边的期望直接求不好求，可以考虑从点的求得。
设E(x)为走x点的期望(Σ次数*概率)，E(u,v)为走这条边的期望。
那么E(x,y)=E(x)/d(x)+E(y)/d(y)，d(i)表示i点的度数。
当然如果x,y其中一个是n的话就不能算了，因为到了n就结束了，不可能再走这条边。
所以现在问题就变成了如何求每个点的期望。
显然E(n)=1,因为n是游戏的终点，最多也最少走一次。
对于其他的x，E(x)=ΣE(v)/d(v) ，条件是存在边(x,v)。
特殊的，对于E(1)，右式还要+1，因为1是起点。
这是一个有后效性的方程，我们只能通过高斯消元求解。。。
(好像实数高斯消元的精度误差都很毒瘤，，，现在已经很迷茫eps到底取多少了hhhh)
#include<bits/stdc++.h>
#define ll long long
#define D long double
#define maxn 505
#define maxm 250005
using namespace std;
const D eps=10e-11;
D a[maxn][maxn],tot;
D ap[maxm],ans[maxn];
int n,m,u[maxm];
int v[maxm],d[maxn];
bool g[maxn][maxn];
inline int zt(D x){
if(x>=-eps&&x<=eps) return 0;
return x>0?1:-1;
}
inline void solve(){
for(int i=1;i<n;i++){
int o=i;
for(int j=i+1;j<n;j++) if(zt(a[j][i]-a[o][i])==1) o=j;
if(o!=i)
for(int k=i;k<=n;k++) swap(a[o][k],a[i][k]);
for(int j=i+1;j<n;j++) if(zt(a[j][i])){
D base=a[j][i]/a[i][i];
for(int k=i;k<=n;k++) a[j][k]-=a[i][k]*base;
}
}
// ans[n]=1.00;
for(int i=n-1;i;i--){
for(int j=n-1;j>i;j--) a[i][n]-=ans[j]*a[i][j];
ans[i]=a[i][n]/a[i][i];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",u+i,v+i);
d[u[i]]++,d[v[i]]++;
g[u[i]][v[i]]=g[v[i]][u[i]]=1;
}
for(int i=1;i<n;i++){
a[i][i]=1.00;
for(int j=1;j<n;j++) if(g[j][i]) a[i][j]=-1.00/(D)d[j];
}
a[1][n]=1.00;
solve();
for(int i=1;i<=m;i++) ap[i]=ans[u[i]]/d[u[i]]+ans[v[i]]/d[v[i]];
sort(ap+1,ap+m+1);
for(int i=1;i<=m;i++) tot+=ap[i]*(m-i+1.00);
printf("%.3Lf
",tot);
return 0;
}