bzoj 3143: [Hnoi2013]游走高斯消元

3143: [Hnoi2013]游走

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1026 Solved: 448
[Submit][Status]

Description

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

Input

第一行是正整数N和M，分别表示该图的顶点数和边数，接下来M行每行是整数u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。

Output

仅包含一个实数，表示最小的期望值，保留3位小数。

Sample Input

3 3
2 3
1 2
1 3

Sample Output

3.333

HINT

边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。

　　这道题我又把题目看错了，我最开始看成了有向无环图，【目测世纪大水题】。。。

　　当这种期望题出现环之后，就变的复杂很多，我们可以对于每一个点求出它的期望经过次数p[]，则p[i]=segma(p[j]/d[j])，有一点还是有点不清楚，就是为什么p[1]在上述式子上必须恰好加1，就只好姑且先记住这样的结论吧。

　　有了上述思路，就可以用高斯消元来做了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 1000

#define MAXV MAXN

#define MAXE 500000

#define abs(x) ((x)>0?(x):(-(x)))

typedef long double real;

struct Edge

{

        int np;

        Edge *next;

}E[MAXE],*V[MAXV];

int tope=-;

void addedge(int x,int y)

{

        E[++tope].next=V[x];

        E[tope].np=y;

        V[x]=&E[tope];

}

int deg[MAXN];

int q[MAXN];

real pp[MAXN];

real a[MAXN][MAXN];

int n,m;

struct edge

{

        int x,y;

        real p;

}w[MAXE];

bool cmp_p(edge e1,edge e2)

{

        return e1.p>e2.p;

}

void pm()

{

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

        {

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

                {

                        printf("%.2Lf ",a[i][j]);

                }

                printf("\n");

        }

        printf("\n");

}

int main()

{

        freopen("input.txt","r",stdin);

        int i,j,k,x,y,z;

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

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

        {

                scanf("%d%d",&x,&y);

                addedge(x,y);

                addedge(y,x);

                deg[x]++;deg[y]++;

                w[i].x=x;w[i].y=y;

        }

        int now;

        Edge *ne;

        for (i=;i<=n-;i++)

        {

                now=i;

                for (ne=V[now];ne;ne=ne->next)

                {

                        if (ne->np!=n)

                                a[now][ne->np]=1.0/deg[ne->np];

                }

                a[now][now]=-;

                a[now][n]=;

        }

        a[][n]=;

        //pm();

        for (i=;i<=n-;i++)

        {

                x=i;

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

                {

                        if (abs(a[j][i])>abs(a[x][i]))

                        {

                                x=j;

                        }

                }

                if (x!=i)

                {

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

                        {

                                swap(a[i][j],a[x][j]);

                        }

                }

                if (!a[i][i])continue;

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

                {

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

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

                        {

                                a[j][k]-=t*a[i][k];

                        }

                }

                //pm();

        }

        pp[n]=;

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

        {

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

                {

                        pp[i]-=pp[j]*a[i][j];

                }

                pp[i]/=a[i][i];

        }

        pp[n]=;

/*        for (i=1;i<=n;i++)

                printf("%.2Lf ",pp[i]);

        printf("\n");*/

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

        {

                w[i].p=pp[w[i].x]/deg[w[i].x] + pp[w[i].y]/deg[w[i].y];

        }

        sort(w,w+m,cmp_p);

        int head=-,tail=-;

        real ans=;

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

        {

                ans+=(i+)*w[i].p;

        }

        printf("%.3Lf",ans);

}

游走