bzoj3143 游走期望dp+高斯消元

题意：

　　一个无向连通图，顶点从1编号到N，边从1编号到M。
　　小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
　　现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。

思路：很显然，我们肯定希望经过次数最多的边的标号最小，但是由于边的数量可能很多，而且好像也不存在什么很好转移的东西，那么我们就需要考虑点。

　　假设E[X]代表从x这个点出发的次数，那么对于{u，v}这样一条边的被经过的次数显然等于$\frac{E[u]}{deg[u]}+\frac{E[v]}{deg[v]}$ deg代表度数，也就是从其他点过来的概率。所以我们只要算出E[x]就可以完成这道题了。

　　我们考虑一般的u（除了起点和终点），显然易得$E[X]=\sum \frac {E[v]}{deg[v]}$。

　　而终点就是的E[X]就是0，起点的期望，除了上述的式子，还需要加入最初始的1.（游戏开局），由于我们这样可以得到n个式子，而且n个式子之间存在推来推去的关系，显然可以考虑高斯消元。

　　所以就按照上面这个式子高斯消元求解，然后把边按经过次数排序就是答案了。

#pragma GCC optimize (2)

#pragma G++ optimize (2)

#pragma comment(linker, "/STACK:102400000,102400000")

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define dep(i,b,a) for(int i=b;i>=a;i--)

#define clr(a,b) memset(a,b,sizeof(a))

#define pb push_back

#define pii pair<int,int >

using namespace std;

typedef long long ll;

ll rd()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

const int inf=0x3f3f3f3f;

int T,n,m;

vector<int >ve[maxn];

struct edge{

    int u,v;

    double g;

    friend bool operator<(const edge &a,const edge &b){

        return a.g>b.g;

    }

}e[maxn*maxn];

const double eps=1e-;

int equ=,var=;

double a[maxn][maxn],x[maxn],deg[maxn];

int Gauss()//高斯消元 返回 0 无解    返回 1有解

{

    int i,j,k,col,max_r;

    for(k=,col=;k<equ&&col<var;k++,col++)

    {

        max_r=k;

        for(i=k+;i<equ;i++)

            if(fabs(a[max_r][col])>fabs(a[max_r][col]))

               max_r=i;

        if(fabs(a[max_r][col])<eps) return ;

        if(k!=max_r)

        {

            for(j=col;j<var;j++)

                swap(a[k][j],a[max_r][j]);

            swap(x[k],x[max_r]);

        }

        x[k]/=a[k][col];

        for(j=col+;j<var;j++) a[k][j]/=a[k][col];

        a[k][col]=;

        for(i=;i<equ;i++)

        {

            if(i!=k)

            {

                x[i]-=x[k]*a[i][col];

                for(j=col+;j<var;j++) a[i][j]-=a[k][j]*a[i][col];

                a[i][col]=;

            }

        }

    }

    return ;

}

int main(){

    cin>>n>>m;

    rep(i,,m){

        scanf("%d%d",&e[i].u,&e[i].v);

        deg[e[i].u]++;

        deg[e[i].v]++;

        ve[e[i].u].push_back(e[i].v);

        ve[e[i].v].push_back(e[i].u);

    }

    x[]=;

    a[n-][n-]=;

    equ=var=n+;

    rep(i,,n-){

        a[i-][i-]=;

        //for(auto &v:ve[i]){

        for(int j=;j<ve[i].size();j++){

        int v=ve[i][j];

            if(v!=n)

            a[i-][v-]=-/deg[v];

        }

    }

    Gauss();

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

        e[i].g=;

        if(e[i].u!=n)

            e[i].g+=x[e[i].u-]/deg[e[i].u];

        if(e[i].v!=n)

            e[i].g+=x[e[i].v-]/deg[e[i].v];

    }

    sort(e+,e++m);

    double ans=;

    rep(i,,m){

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

    }

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

}

巴特西

bzoj3143 游走期望dp+高斯消元

最新文章

热门文章

巴特西

bzoj3143 游走 期望dp+高斯消元

最新文章

热门文章

bzoj3143 游走期望dp+高斯消元