bzoj3143/洛谷3434 游走 高斯消元求期望

题目分析

首先，假如我们求出每条边的经过期望就可以贪心求解了。
而每条边的经过期望是很难求的，所以我们把边期望转化成点经过期望。
点经过期望设为f[i],点i的度数设为du[i]
那么：

$$f[i]= \sum ^{i->j}_j \frac{f[j]}{du[j]}$$
而肯定有f[n]=1，因为到了n就停了。
1号点除了从别的点到达以外还能过一次，所以 $$f[1]=f[i]= \sum ^{1->j}_j \frac{f[j]}{du[j]}+1$$
然后因为n号点进去了就不能出来了，所以如果j是n号点就不用算。
再然后算边：
$$w=\frac{f[u]}{du[u]}+\frac{f[v]}{du[v]}$$
同理，如果u或者v是n号点就不用算

代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m;double ans;
int s[250000],t[250000],du[505];
double a[505][505],eps=1e-7,bian[250000];
void guss(){
    int i,j,k,bj;double t;
    for(k=0;k<n;k++){
        bj=k;
        for(i=k+1;i<n;i++)
            if(fabs(a[i][k])>fabs(a[bj][k]))bj=i;
        if(bj!=k)for(j=k;j<=n;j++)swap(a[bj][j],a[k][j]);
        t=a[k][k];
        for(j=k;j<=n;j++)a[k][j]/=t;
        for(i=0;i<n;i++)if(i!=k){
            t=a[i][k];if(fabs(t)<eps)continue;
            for(j=k;j<=n;j++)a[i][j]-=a[k][j]*t;
        }
    }
}
int main()
{
    int i,j;
    n=read();m=read();
    for(i=1;i<=m;i++){
        s[i]=read();t[i]=read();
        du[s[i]]++;du[t[i]]++;
    }
    for(i=0;i<n;i++)a[i][i]=1.0;
    a[0][n]=1.0;a[n-1][n]=1.0;
    for(i=1;i<=m;i++)if(s[i]!=n&&t[i]!=n){
        a[s[i]-1][t[i]-1]-=1.0/du[t[i]];
        a[t[i]-1][s[i]-1]-=1.0/du[s[i]];
    }
    guss();
    for(i=1;i<=m;i++){
        if(s[i]!=n)bian[i]+=a[s[i]-1][n]/du[s[i]]*1.0;
        if(t[i]!=n)bian[i]+=a[t[i]-1][n]/du[t[i]]*1.0;
    }
    sort(bian+1,bian+1+m);
    for(i=1;i<=m;i++)ans+=bian[i]*(m-i+1.0);
    printf("%.3f",ans);
    return 0;
}