首页 > 代码库 > BZOJ 3143: [Hnoi2013]游走

BZOJ 3143: [Hnoi2013]游走

2024-09-06 01:02:03   219人阅读

3143: [Hnoi2013]游走

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2604  Solved: 1127
[Submit][Status][Discuss]

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

非官方数据

分析：

如果我们要求最小期望值，那么就要求出每条边的期望经过次数，然后从大到小排序，从小到大赋值...

每条边的期望经过次数可以转化为每个点的期望经过次数，记$f[i]$为$i$号节点的期望经过次数，$d[i]$为$i$号节点的度数，那么$e[x][y]=\frac {f[x]}{d[x]}+\frac {d[y]}{d[y]}$...

每个节点的期望经过次数就是一个简单的期望$DP$模型，因为有环，所以我们要高斯消元一发...

写这题写了一个小时，原因是我一直认为我的$gauss$函数写错了，然后一直调不对，在晚自习下课的最后一分钟我发现我没有调用$gauss$函数...然后我被$ysq$了一个小时好水连高斯消元都不会...

代码：

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>//by NeighThorn#define eps 1e-5using namespace std;const int maxn=500+5,maxm=125000+5;int n,m,du[maxn],mp[maxn][maxn];double ans,a[maxn][maxn];struct M{		int x,y;	double p;		friend bool operator < (M a,M b){		return a.p>b.p;	}	}e[maxm];inline void gauss(void){	for(int i=1;i<n;i++){		int k=i;		while(fabs(a[k][i])<eps&&k<n-1) k++;		if(k!=i)			for(int j=1;j<=n;j++)				swap(a[i][j],a[k][j]);		for(int l=1;l<n;l++)			if(l!=i){				double lala=a[l][i]/a[i][i];				for(int s=1;s<=n;s++)					a[l][s]-=a[i][s]*lala;			} 	}}signed main(void){	scanf("%d%d",&n,&m);ans=0;	for(int i=1,x,y;i<=m;i++)		scanf("%d%d",&x,&y),mp[x][y]=mp[y][x]=1,du[x]++,du[y]++,e[i].x=x,e[i].y=y;	memset(a,0,sizeof(a));	for(int i=1;i<n;a[i][i]=1.0,i++)		for(int j=1;j<n;j++)			if(mp[i][j])				a[i][j]=-1.0/(double)du[j];	a[1][n]=1.0;gauss();	for(int i=1;i<n;i++)		a[i][i]=a[i][n]/a[i][i];	for(int i=1;i<=m;i++)		e[i].p=a[e[i].x][e[i].x]/(double)du[e[i].x]+a[e[i].y][e[i].y]/(double)du[e[i].y];	sort(e+1,e+m+1);	for(int i=1;i<=m;i++)		ans+=i*e[i].p;	printf("%.3f\n",ans);	return 0;}

　　

By NeighThorn

BZOJ 3143: [Hnoi2013]游走


联系
我们