游走[HNOI2013]

【题目描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

【样例输出】

3.333

【提示】

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

【题解】

对答案贡献大的边编号越小越好，贡献小的边编号自然需要较大，这样想明显需要求出各边经过次数的期望。

首先删去终点的出边，对于每一条边，设其两个节点为u和v：可能从u走到v，也可能从v走到u，从u走到v的期望次数等于经过点u的次数/u的度数，问题转化成求每个点的期望经过次数。

和臭气弹类似地，对于起点,一开始经过一次,也可能从其他点走过来。这是n个变量n个方程的方程组，高斯消元解方程组。
f[1]=1+sigma(f[j]/degree(j),j和1有边)
f[i]=sigma(f[j]/degree(j),j和i有边，i>=2)

求出各边期望的经过次数之后从大到小sort一下，把它的编号作为边权，计算结果即可。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int sj=;

const double je=1e-;

int n,m,a1,a2,e,h[sj],q[sj*sj],z[sj*sj];

double cd[sj],a[sj][sj],c[sj],jg,xx[sj*sj];

struct B

{

    int ne,v;

}b[sj*sj*];

void add(int x,int y)

{

     b[e].v=y;

     b[e].ne=h[x];

     h[x]=e++;

     cd[x]++;

}

void init()

{

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

    memset(h,-,sizeof(h));

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

    {

       scanf("%d%d",&a1,&a2);

       q[i]=a1;

       z[i]=a2;

       if(a1!=n)  add(a1,a2);

       if(a2!=n)  add(a2,a1);

    }

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

    {

       a[i][i]=;

       for(int j=h[i];j!=-;j=b[j].ne)

          a[b[j].v][i]-=/cd[i];

    }

    c[]=;

    a[n][n]=;

}

void jh(double &x,double &y)

{

     double temp=y;

     y=x;

     x=temp;

}

void gs()

{

     int zd;

     double temp;

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

     {

        zd=i;

        temp=fabs(a[i][i]);

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

          if(temp<fabs(a[j][i]))

          {

             zd=j;

             temp=fabs(a[j][i]);

          }

        if(zd!=i)

        {

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

            jh(a[i][j],a[zd][j]);

           jh(c[i],c[zd]);

        }

        if(fabs(a[i][i])<je) continue;

        temp=a[i][i];

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

          a[i][j]/=temp;

        c[i]/=temp;

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

          if(i!=j)

          {

             temp=a[j][i];

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

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

             c[j]-=c[i]*temp;

          }

     }

}

int main()

{

    //freopen("t.txt","r",stdin);

    freopen("walk.in","r",stdin);

    freopen("walk.out","w",stdout);

    init();

    gs();

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

    {

        if(cd[q[i]])

          xx[i]+=c[q[i]]/cd[q[i]];

        if(cd[z[i]])

          xx[i]+=c[z[i]]/cd[z[i]];

    }

    sort(xx+,xx+m+,greater<double>());

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

      jg+=xx[i]*i;

    printf("%.3lf",jg);

    //while(1);

    return ;

}