【bzoj3143】游走

  • 高斯消元重修系列第三题

这题很神，不看题解根本想不出来

如果我们能计算出经过每条边的期望次数，那么贪心编号即可

如果我们能计算出每个点的期望经过次数，那么就可以计算出每条边经过的期望次数（每个点每次经过，除了1和n必然一进一出）

如何求解每个点的经过次数？

设$x_i$为第i个点的经过次数的期望值，则 $x_i=\sum x_j \times \frac{1}{d_j} (i，j有边相连)$

边界条件:

（1）$x_n=0$

（2）对于1号点,$x_1-1=\sum x_j \times \frac{1}{d_j}$

高斯消元求出所有的x之后，设每条边的经过次数的期望值$c_i$

则：$c_i=x_i \times \frac{1}{d_i} + x_j \times \frac{1}{d_j} (i，j为边的两端点)$ 

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 510
#define eps 1e-6
using namespace std;
struct node{int x,y;}e[MAXN*MAXN];
int n,m,d[MAXN];
double ans,c[MAXN*MAXN],a[MAXN][MAXN];
bool cmp(double a,double b){return a>b;}
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getc();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
	return x*f;
}
void init(){
	n=read();  m=read();
	for(int i=1;i<=m;++i){
		e[i].x=read();e[i].y=read();
		d[e[i].x]++; d[e[i].y]++;
	}
	for(int i=1;i<=m;++i){
		a[e[i].x][e[i].y]+=1.0/d[e[i].y];
		a[e[i].y][e[i].x]+=1.0/d[e[i].x];
	}
	for(int i=1;i<=n;++i) a[n][i]=0;
	for(int i=1;i<=n;++i) a[i][i]=-1;
	a[1][n+1]=-1;
}
bool gauss(){
	int now=1;
	for(int i=1,temp;i<=n;++i){
		for(temp=now;temp<=n;++temp)if(fabs(a[temp][i])>eps)break;
		if(temp>n) continue;
		if(now!=temp) swap(a[temp],a[now]);
		double t=a[now][i];
		for(int j=i+1;j<=n+1;++j) a[now][j]/=t;
		for(int j=1;j<=n;++j)if(j!=now){
			double t=a[j][i];
			for(int k=i+1;k<=n+1;++k) a[j][k]-=t*a[now][k];
		}
		++now;
	}
	for(int i=now;i<=n;++i) if(fabs(a[i][n+1])>eps) return 0;
	return 1;
}
void solve(){
	gauss();
	for(int i=1;i<=m;++i) c[i]=a[e[i].x][n+1]/d[e[i].x]+a[e[i].y][n+1]/d[e[i].y];
	sort(c+1,c+m+1,cmp);
	for(int i=1;i<=m;++i) ans+=c[i]*i;
	printf("%.3lf\n",ans);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	init(); solve();
	return 0;
}

本文标题:【bzoj3143】游走

文章作者:chty

发布时间:2017年03月10日 - 22时27分

最后更新:2018年07月01日 - 15时37分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,