【BZOJ 3143】【Hnoi2013】游走 期望+高斯消元

时间：2023-03-09 03:46:49
【BZOJ 3143】【Hnoi2013】游走 期望+高斯消元

如果纯模拟，就会死循环，而随着循环每个点的期望会逼近一个值，高斯消元就通过列方正组求出这个值。

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

using namespace std;

const double eps=1e-9;

bool vis[503];

double f[503],a[503][503],ans[500*500];

int N,M,cnt=0,du[503],a1[500*500],a2[500*500];

double fabs(double x){return x>0?x:-x;}

int getint(){char c;while (!isdigit(c=getchar()));int a=c-'0';while(isdigit(c=getchar()))a=a*10+c-'0';return a;}

void prepare(){

    for(int i=1;i<=M;++i){

        a[a1[i]][a2[i]]+=1.0/du[a2[i]];

        a[a2[i]][a1[i]]+=1.0/du[a1[i]];

    }

    for(int i=1;i<=N;++i)a[N][i]=0;

    for(int i=1;i<N;++i)a[i][i]=-1.0;

    a[1][N+1]=-1.0;a[N][N]=1.0;

}

void swapp(double &x,double &y){double z=x;x=y;y=z;}

void gauss(){

    for(int i=1;i<=N;++i){

        int now=i;

        for(int j=i+1;j<=N;++j)if(fabs(a[j][i])>fabs(a[now][i]))now=j;

        if (now!=i)for(int j=i;j<=N+1;++j)swapp(a[now][j],a[i][j]);

        for(int j=i+1;j<=N;++j){

            double t=a[j][i]/a[i][i];

            for(int k=i;k<=N+1;++k)a[j][k]-=t*a[i][k];

        }

    }

    for(int i=N;i>=1;--i){

        for(int j=N;j>i;--j){

            a[i][N+1]-=a[j][N+1]*a[i][j];

        }a[i][N+1]/=a[i][i];

    }

}

bool cmp(double a,double b){return a>b;}

int main(){

    memset(a,0,sizeof(a));

    memset(du,0,sizeof(du));

    N=getint();M=getint();

    for(int i=1;i<=M;++i){

        a1[i]=getint();a2[i]=getint();

        du[a1[i]]++;du[a2[i]]++;

    }prepare();

    gauss();

    cnt=0;

    for(int i=1;i<=M;++i){

        ans[++cnt]=a[a1[i]][N+1]/du[a1[i]]+a[a2[i]][N+1]/du[a2[i]];

    }

    sort(ans+1,ans+M+1,cmp);

    double sa=0;

    for(int i=1;i<=M;++i) sa+=ans[i]*i*1.0;

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

    return 0;

}

　　这样就可以了

相关文章