bzoj 3143 随机游走

题意:

　　给一个简单无向图,一个人从1号节点开始随机游走(即以相同概率走向与它相邻的点),走到n便停止,问每条边期望走的步数.

首先求出每个点期望走到的次数,每条边自然是从它的两个端点走来.

 /**************************************************************

     Problem: 3143

     User: idy002

     Language: C++

     Result: Accepted

     Time:736 ms

     Memory:9956 kb

 ****************************************************************/

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #define N 510

 #define M N*N

 using namespace std;

 int n, m;

 int head[N], dest[M], next[M], etot;

 int dgr[N], uu[M], vv[M], qu[M];

 double ww[M];

 double a[N][N];

 void adde( int u, int v ) {

     etot++;

     dest[etot] = v;

     next[etot] = head[u];

     head[u] = etot;

 }

 void gauss() {

     int i, j, k;

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

         j=i;

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

             if( fabs(a[k][i])>fabs(a[j][i]) ) j=k;

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

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

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

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

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

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

         }

     }

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

         a[i][n+] /= a[i][i];

         a[i][i] = 1.0;

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

             a[j][n+] -= a[j][i]*a[i][n+];

             a[j][i] = 0.0;

         }

     }

 }

 bool cmp( int a, int b ) {

     return ww[a] > ww[b];

 }

 int main() {

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

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

         scanf( "%d%d", uu+i, vv+i );

         adde( uu[i], vv[i] );

         adde( vv[i], uu[i] );

         dgr[uu[i]]++;

         dgr[vv[i]]++;

     }

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

         a[i][i] = -1.0;

     a[][n+] = -;

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

         for( int t=head[u]; t; t=next[t] ) {

             int v=dest[t];

             if( v==n ) continue;

             a[u][v] += 1.0/dgr[v];

         }

     }

     gauss();

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

         int u=uu[i], v=vv[i];

         if( u!=n ) ww[i]+=a[u][n+]/dgr[u];

         if( v!=n ) ww[i]+=a[v][n+]/dgr[v];

     }

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

         qu[i] = i;

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

     double ans = 0.0;

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

         ans += i * ww[qu[i]];

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

 }