BZOJ 3143 游走

发表于 | 更新于

Link 吃了期望的亏，回来怼期望。 一个随机变量，存在v→+∞v\rightarrow +\infty，但此时P→0P\rightarrow 0，这个变量的期望不会是∞\infty 期望是线性函数，E[aX+bY]=aE[X]+bE[Y]E[aX+bY]=aE[X]+bE[Y] 求一条边的期望值可以转化为求点的

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
const int INF=522133279,MAXN=500+1,MAXM=MAXN*MAXN;
typedef long double ld;
typedef ld Matrix[MAXN][MAXN];
const ld eps=1e-10;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::max;
using std::min;
using std::swap;
using std::sort;
using std::greater;
using std::cout;
using std::endl;
template <class T> struct List
{
	List<T> *pre;
	T val;
	List(List<T> *_pre=0,T _val=0):pre(_pre),val(_val){}
};
List<int> *ME=new List<int>[MAXM<<1],*G[MAXN];
inline void Add(List<int> *&cur,int val)
{
	cur=new (ME++)List<int>(cur,val);
}
int deg[MAXN];
ld E[MAXN];
inline int fcmp(const ld& x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> inline void swap_n(T *a,T *b,int n)
{
	for(int i=1;i<=n;i++) swap(a[i],b[i]);
}
void Gauss(Matrix &A,int n)
{
	for(int i=1;i<=n;i++)
	{
		int mx=i;
		for(int j=i+1;j<=n;j++)
			if(fcmp(fabs(A[j][i])-fabs(A[mx][i]))>0) mx=j;
		if(mx!=i) swap_n(A[i],A[mx],n+1);
		for(int j=i+1;j<=n;j++)
		{
			ld f=A[j][i]/A[i][i];
			for(int k=1;k<=n+1;k++) A[j][k]-=f*A[i][k];
		}
	}
	for(int i=n;i;i--)
	{
		for(int j=i+1;j<=n;j++) A[i][n+1]-=A[i][j]*A[j][n+1];
		A[i][n+1]/=A[i][i];
	}
}
int main()
{
	static Matrix A;
	static ld exp[MAXM];int cexp=0;
	freopen("input","r",stdin);
	int t1,t2,t3,n,m;red(n),red(m);
	for(int i=1;i<=m;i++)
	{
		red(t1),red(t2);
		Add(G[t1],t2);
		Add(G[t2],t1);
		deg[t1]++,deg[t2]++;
	}
	//只有第E[1\N]存在常数项，为1
	for(int i=1;i<n;i++)
	{
		A[i][i]=1;
		for(List<int> *it=G[i];it;it=it->pre)
		{
			int u=it->val;
			if(u==n) continue;
			A[i][u]=(ld)(-1.0/deg[u]);
		}
	}
	A[1][n+1]=A[n][n+1]=A[n][n]=1;
	Gauss(A,n);
	for(int i=1;i<=n;i++) E[i]=A[i][n+1];
	for(int pos=1;pos<=n;pos++)
		for(List<int> *it=G[pos];it;it=it->pre)
		{
			int u=it->val;
			if(pos>u) continue;

			exp[++cexp]=E[pos]/deg[pos];
			if(u!=n)
				exp[cexp]+=E[u]/deg[u];//..

		}
	sort(exp+1,exp+cexp+1,greater<ld>());
	ld ANS=0;
	for(int i=1;i<=m;i++)
		ANS+=exp[i]*i;
	printf("%.3lf\n",(double)ANS);
	return 0;
}