期望dp+高斯消元——bzoj3143

比较经典的题，题解看网上的。。https://www.cnblogs.com/GXZlegend/p/7054536.html

自己sort弄错了。。还以为是高斯消元写歪了。。

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

const double esp = 1e-;

struct Edge{int u,v;double E;}e[maxn*maxn];

int mp[maxn][maxn],d[maxn],n,m;

double E[maxn][maxn],b[maxn];

int cmp(Edge a,Edge b){return a.E>b.E;}

void guass(){

    for(int i=;i<=n;i++){

        int maxx=i;

        for(int j=i;j<=n;j++){

            if(fabs(E[j][i])>esp&&fabs(E[j][i])>fabs(E[maxx][i]))maxx=j;

        }

        if(maxx!=i){

            swap(E[maxx],E[i]);

            swap(b[maxx],b[i]);

        }

        if(fabs(E[i][i])<esp)continue;

        for(int j=i+;j<=n;j++){

            if(fabs(E[j][i])<esp)continue;

            double rate=E[j][i]/E[i][i];

            for(int k=i;k<=n;k++)

                E[j][k]-=rate*E[i][k];

            b[j]-=rate*b[i];

        }

    }

    for(int i=n;i>=;i--){

        if(fabs(E[i][i])<esp)continue;

        for(int j=i+;j<=n;j++)

            b[i]-=E[i][j]*b[j];

        b[i]/=E[i][i];

    }

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        mp[u][v]=mp[v][u]=;

        d[u]++;d[v]++;

        e[i].u=u;e[i].v=v;

    }

    //建立矩阵

    E[n][n]=b[]=;

    for(int i=;i<n;i++){

        E[i][i]=;

        for(int j=;j<=n;j++)

            if(mp[i][j])E[i][j]-=1.0/d[j];

    }

    guass();

    for(int i=;i<=m;i++){

        int u=e[i].u,v=e[i].v;

        e[i].E=b[u]/d[u] + b[v]/d[v];

    }

    sort(e+,e++m,cmp);

    double ans=;

    for(int i=;i<=m;i++)

        ans+=e[i].E*i;

    printf("%.3lf\n",ans);

}