BZOJ 3143 游走

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。

Source

题解

若已知每条边期望走了多少次那么就可以贪心的求出解。

设\(w_i\) 表示第i条边期望走多少次。

那么有\(w_i = dp_u / d_u + dp_v / d_v\)

dp 是这个点期望走了多少次(走出！！)。

\(dp_i = \display \sum_{e(j , i)} dp_j / d_j\)

根据这个可以得到n个方程，用高斯消元消出答案即可。

注意\(a[1][n+1] = -1; dp[n][n] = 任意非0\)

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<vector>

#include<set>

#include<map>

using namespace std;

const int N = 520 , M = N * N;

inline int read()

{

    register int x = 0 , f = 0; register char c = getchar();

    while(c < '0' || c > '9') f |= c == '-' , c = getchar();

    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();

    return f ? -x : x;

}

int n , m;

int d[N] , eu[M] , ev[M];

double a[N][N] , w[M] , x[N];

void calc(int n , int m)

{

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

	{

		int res = i;

		for(int j = i + 1 ; j <= n ; ++j) if(fabs(a[j][i]) > fabs(a[res][i])) res = j;

		if(i != res) swap(a[i] , a[res]);

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

		{

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

			for(int s = i ; s <= m ; ++s) a[j][s] -= a[i][s] * k;

		}

	}

	for(int i = m-1 ; i >= 1 ; --i)

	{

		for(int j = i+1 ; j < m ; ++j) a[i][m] -= a[j][j] * a[i][j];

		a[i][i] = a[i][m] / a[i][i];

	}

	for(int i = 1 ; i <= n ; ++i) x[i] = a[i][i];

	return ;

}

int main()

{

	n = read(); m = read();

	for(int i = 1 ; i <= m ; ++i) eu[i] = read() , ev[i] = read() , d[ev[i]]++ , d[eu[i]]++;

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

	{

		a[eu[i]][ev[i]] += 1.0 / d[ev[i]];

		a[ev[i]][eu[i]] += 1.0 / d[eu[i]];

	}

	for(int i = 1 ; i < n ; ++i) a[i][i] = -1 , a[n][i] = 0; a[n][n] = 1; a[1][n+1] = -1;

	calc(n , n + 1);

	for(int i = 1 ; i <= m ; ++i) w[i] = x[eu[i]] / d[eu[i]] + x[ev[i]] / d[ev[i]];

	sort(w + 1 , w + 1 + m);

	double ans = 0;

	for(int i = 1 ; i <= m ; ++i) ans += i * w[m-i+1];

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

	return 0;

}

巴特西