bzoj 3143 [Hnoi2013]游走【高斯消元+dp】

参考：http://blog.****.net/vmurder/article/details/44542575

和2337有点像

设点u的经过期望(还是概率啊我也分不清，以下都分不清）为\( x[u] \) ，度为 \( in[u] \)，边\( (u,v) \) 的经过期望为 \( \frac{x[u]}{in[u]}+\frac{x[v]}{in[v]} \)

那么转换为求每个点的经过期望，\( x[u]=\sum_{v}^{v\subset son(u)}\frac{x[v]}{in[v]} \)

高斯消元即可。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int N=505,M=250005;
using namespace std;
int n,m;
int U[M],V[M],d[N];
double a[N][N],x[N],w[M],ans;
void Gauss(int n,int m)
{
    for(int i=1;i<m;i++)
    {
		int k=i;
        for(int j=i+1;j<=n;j++)
			if(fabs(a[k][i])<fabs(a[j][i]))
				k=j;
        if(i!=k)
			for(int j=i;j<=m;j++)
				swap(a[i][j],a[k][j]);
        for(int j=i+1;j<=n;j++)
        {
            double rate=a[j][i]/a[i][i];
            for(k=i;k<=m;k++)
				a[j][k]-=a[i][k]*rate;
        }
    }
    for(int i=m-1;i;i--)
    {
        for(int j=i+1;j<m;j++)
			a[i][m]-=a[i][j]*x[j];
        x[i]=a[i][m]/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]]++;
    }
    for(int i=1;i<n;i++)
		a[i][i]=-1;
    for(int i=1;i<=m;i++)
    {
        a[U[i]][V[i]]+=1.0/d[V[i]];
        a[V[i]][U[i]]+=1.0/d[U[i]];
    }
    for(int i=1;i<=n;i++)
		a[n][i]=0;
    a[1][n+1]=-1,a[n][n]=1;
    Gauss(n,n+1);
    for(int i=1;i<=m;i++)
		w[i]=x[U[i]]/d[U[i]]+x[V[i]]/d[V[i]];
    sort(w+1,w+m+1);
    for(int i=1;i<=m;i++)
		ans+=(m-i+1)*w[i];
    printf("%.3lf\n",ans);
    return 0;
}