[HNOI2013]游走

[HNOI2013]游走

考虑随机游走时一条边 $ (x,y) $ 被经过，只有两种情况，要么是我们走到了点 $ x $ ，然后随机钦定了 $ y $ ，要么就是反过来。我们假设一个点的度数为 $ deg[i] $ ，假设一个点期望会经过 $ t[u] $ 次，所以一个边所贡献的权值就是 $ w imes ( frac{t[x]}{deg[x]} + frac{t[y]}{deg[y]} ) $ 。

所以现在我们的目标就是求 $ t $ 。发现 $ n leq 500 $ 我们可以考虑高消，具体而言，可以列出

[t[u] = sum frac{t[v]}{deg[v]} ]

特别的，对于第一个点必然会被经过一次， $ t[1] = 1 + sum frac{t[v]}{deg[v]} $ ，而 $ t[n] = 0 $，因为到达了 $ n $ 号点就结束了。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
using namespace std;
#define MAXN 506
int n , m;
#define eps 1e-6
int deg[MAXN];
double A[MAXN][MAXN];
int gauss(  ) {
    for( int i = 1 ; i <= n ; ++ i ) { // cur : 第 i 行
        int mxpos = i;
        for( int j = i ; j <= n ; ++ j ) if( fabs( A[j][i] ) - fabs( A[mxpos][i] ) > eps )
                mxpos = j;
        for( int j = 1 ; j <= n + 1 ; ++ j )
            swap( A[i][j] , A[mxpos][j] );
        double c = A[i][i];
        if( c == 0 ) { return 0; }
        A[i][i] = 1;
        for( int j = i + 1 ; j <= n + 1 ; ++ j )
            A[i][j] /= c;
        for( int j = 1 ; j <= n ; ++ j ) if( j != i ) { // cur : 第 j 行
                double cc = A[j][i]; A[j][i] = 0;
                for( int k = i + 1 ; k <= n + 1 ; ++ k ) // cur : 第 k 列
                    A[j][k] -= cc * A[i][k];
            }
    }
    return 1;
}
pair<int,int> E[MAXN * MAXN];
double w[MAXN * MAXN];
int G[MAXN][MAXN];
int main() {
    cin >> n >> m;
    for( int i = 1 , u , v ; i <= m ; ++ i ) {
        scanf("%d%d",&u,&v);
        ++ deg[u] , ++ deg[v]; G[u][v] = G[v][u] = 1;
        E[i] = make_pair( u , v );
    }
    A[1][n + 1] = -1;
    for( int i = 1 ; i < n ; ++ i )
        for( int j = 1 ; j < n ; ++ j )
            if( G[i][j] )
                A[i][j] = 1.0 / deg[j];
            else if( i == j ) A[i][j] = -1.0;
    A[n][n] = 1;
//    for( int i = 1 ; i <= n ; ++ i ) {
//        for (int j = 1; j <= n + 1; ++j) printf("%.3f ", A[i][j]); puts("");
//    }
    gauss( );
//    for( int i = 1 ; i <= n ; ++ i ) cout << A[i][n + 1] << endl;
    for( int i = 1 ; i <= m ; ++ i ) {
        int u = E[i].first , v = E[i].second;
        w[i] = A[u][n + 1] / deg[u] + A[v][n + 1] / deg[v];
    }
    sort( w + 1 , w + 1 + m );
    double res = 0;
    for( int i = 1 ; i <= m ; ++ i ) res += ( m - i + 1 ) * w[i];
    printf("%.3f",res);
}