• 欢迎光临~

「CERC2017」Gambling Guide

开发技术 开发技术 2022-12-11 次浏览

「CERC2017」Gambling Guide

给定一张 (n) 个点,(m) 条边的无向图,在每个时刻每个点会随机开放一条出边,你可以不动或沿着开放的边走(均花费 (1) 的时间),求最优策略下从 (1) 到达 (n) 的期望时间


图上问题考虑逆推,设节点 (i) 到达 (n) 的期望时间为 (dp_i),节点 (i) 的出度为 (deg_i)

则有 (dp_i=frac{sum min(dp_i,dp_j)}{deg_i}+1)(i)(j) 之间有边相连)

(cnt_i) 为满足 (dp_j < dp_i)(i)(j) 之间有边相连的 (j) 的数量,(sum_i) 为满足 (dp_j < dp_i)(i)(j) 之间有边相连的 (j)(sum dp_j)

则有 (dp_i=frac{sum_i}{deg_i}+frac{(deg_i-cnt_i) times dp_i}{deg_i}+1)

移项得 ((1-frac{deg_i-cnt_i}{deg_i}) times dp_i=frac{sum_i}{deg_i}+1)

那么 (frac{cnt_i}{deg_i} times dp_i=frac{sum_i+deg_i}{deg_i})

化简得 (dp_i=frac{sum_i+deg_i}{cnt_i})

考虑用 (dijkstra),只是我们每次转移的时候去以当前节点更新与它相连的节点应该为未访问过的节点,因为如果已经访问过了,而且边权都为 (1)(> 0)),那么只会增加它的 (dp) 值,不属于最优策略

这里再证明一下使用 (dijkstra) 的正确性,(dijkstra) 是一种贪心最短路,需要满足它的松弛性,也就是每次更新当前节点后,它的点权要小于更新前的点权且大于更新它的节点的点权,也就是边权不为负,但是这里和普通最短路不同

令用 (j) 点更新 (i) 点,且更新后的值为 (dp_i')

(dp_i=frac{sum_i+deg_i}{cnt_i})(dp_i'=frac{sum_i+deg_i+dp_j}{cnt_i+1}),那么 (dp_i-dp_i'=frac{dp_i-dp_j}{cnt_i+1})

因为 (dp_i > dp_j),所以 (0 < dp_i-dp_i' < dp_i-dp_j),即 (dp_j < dp_i' < dp_i),满足松弛性

示例代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,vis[300001];
double dp[300001],sum[300001],cnt[300001];
vector <int> G[300001];
priority_queue <pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > > Q;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	Q.push({0,n});
	while(!Q.empty()){
		int rt=Q.top().second;
		Q.pop();
		if(vis[rt]) continue;
		vis[rt]=1;
		for(int i=0;i<G[rt].size();i++){
			int to=G[rt][i];
			if(!vis[to]){
				cnt[to]++;
				sum[to]+=dp[rt];
				dp[to]=(1.0*G[to].size()+sum[to])/cnt[to];
				Q.push({dp[to],to});
			}
		}
	}
	printf("%.10lf",dp[1]);
	return 0;
}
程序员灯塔
转载请注明原文链接:「CERC2017」Gambling Guide
喜欢 (0)