首页 > 其他分享 >绿豆蛙的归宿(别问我为什么会写这玩意)

绿豆蛙的归宿(别问我为什么会写这玩意)

时间:2024-05-27 15:24:01浏览次数:21  
标签:cnt degree int 绿豆蛙 别问 edge 玩意 head out

声明一下,概率与期望这块属实没有看懂,如果有什么唐氏错误多多包容

image
image

正推

image

不很显然,对于边(i,j),j的期望值是i的期望值加上边权除以i的出度(从i出发边的条数),我对于这个的理解是假设从i出发有k条边,j是其中一个,那么到j的可能就是
\(\frac{1}{k}\) 即\(\frac{1}{out[i]}\)
所以会有 \(f[j]+=\frac{f[i]}{out[i]}\)
又因为已经经过这个边,所以还有
\(f[j]+=\frac{p[i]*w}{out[i]}\)
其中p[i]表示从1到i的概率,p[1]=1,\(p[j]=\sum\frac{p[i]}{out[i]}[w!=0]\)

看的DZ的
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
struct node{
	int from;
	int to;
	int w;
}edge[N];
double degree[N],out[N],head[N],p[N];
double f[N];
queue<int> q;
int n,m,cnt;
void add(int from,int to,int w){
	cnt++;
	edge[cnt].from=head[from];
	edge[cnt].to=to;
	edge[cnt].w=w;
	head[from]=cnt;
	degree[to]++,out[from]++;
}
int main(){
	int from,to,w;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>from>>to>>w;
		add(from,to,w);
	}
	for(int i=1;i<=n;i++){
		if(!degree[i]) q.push(i);
	}
	p[1]=1;
	while(!q.empty()){
		int e=q.front();
		q.pop();
		for(int i=head[e];i;i=edge[i].from){
			int to=edge[i].to;
			f[to]+=(f[e]+edge[i].w*p[e])/out[e];
			p[to]+=p[e]/out[e];
			degree[to]--;
			if(degree[to]==0) q.push(to);
		} 
	}
	cout<<setprecision(2)<<fixed<<f[n]<<endl;
}

逆推

image

根据正推和分析,实际上我们会发现,需要用到p数组的原因是我们实际上将一个点的期望值拆给了其他与它相连的点(如图中1拆给了2345,p为1/4),那我们能不能反过来,将2345的期望值加给1呢?很显然是可以的,这就是逆推,
首先,反向建边
image
那么对于一条原边(i,j),i的期望值就是j的期望值和边权的加和除以i的出度
\(f[i]+=(f[j]+edge[i].w)/out[i]\) (这里的i,j和建边的i,j是反过来的)

然后就没了

逆推
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
struct node{
	int from;
	int to;
	int w;
}edge[N];
int degree[N],out[N],head[N];
double f[N];
queue<int> q;
int n,m,cnt;
void add(int from,int to,int w){
	cnt++;
	edge[cnt].from=head[from];
	edge[cnt].to=to;
	edge[cnt].w=w;
	head[from]=cnt;
	degree[to]++,out[to]++;
}
int main(){
	int from,to,w;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>from>>to>>w;
		add(to,from,w);
	}
	q.push(n);
	while(!q.empty()){
		int e=q.front();
		q.pop();
		for(int i=head[e];i;i=edge[i].from){
			int to=edge[i].to;
			f[to]+=(f[e]+edge[i].w)/out[to];
			degree[to]--;
			if(degree[to]==0) q.push(to);
		} 
	}
	cout<<setprecision(2)<<fixed<<f[1]<<endl;
}

标签:cnt,degree,int,绿豆蛙,别问,edge,玩意,head,out
From: https://www.cnblogs.com/PeppaEvenPigShiGeNiuBDePig/p/18212747

相关文章

  • 绿豆蛙的归宿
    绿豆蛙的归宿题目背景随着新版百度空间的上线,Blog宠物绿豆蛙完成了它的使命,去寻找它新的归宿。题目描述给出张\(n\)个点\(m\)条边的有向无环图,起点为\(1\),终点为\(n\),每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。绿豆蛙从起点出发,走......
  • 经营贷的风险及老百姓当下不要碰这玩意
    一、经营贷的基本概念和发展历程首先,我们要知道什么是经营贷?这里我们所讨论的“经营贷”全称为房产抵押经营贷,是指借款人以自己名下的房产作为抵押物,向银行或其他金融机构申请的用于企业经营活动的贷款产品。这类贷款的主要目的是为小微企业主或个体工商户提供流动资金支持,帮助......
  • 使用支持向量机算法解决手写体识别问题
    文章目录支持向量机导入图片测试算法fromgoogle.colabimportdrivedrive.mount("/content/drive")Drivealreadymountedat/content/drive;toattempttoforciblyremount,calldrive.mount("/content/drive",force_remount=True).支持向量机fromnumpy......
  • 记一下mysql隔离级别问题
      MSQL默认隔离级别是  可重复读; 可重复读即 同一次查询,再次查询结果一致;不会查询到别的事务提交的内容;原理:开始事务后,做一次select产生一个readview,这个readview已经确定了能读取的undolog链;简单理解就是只能读取到当前事务版本之前的数据;当另一个事务插入数据......
  • 【JDK】windows安装多版本jdk,识别问题
    1、多版本在编辑JAVA_HOME时,可用版本号后缀编辑多个,在使用时,直接修改path上的JAVA_HOME名称即可  2、cmd输入java-version还是没改过来的问题原因是①C:\ProgramFiles\CommonFiles\Oracle这个目录有java的识别程序,删掉这俩文件夹即可 ②C:\ProgramFiles(x86)\Com......
  • Confluence7.4.6突然爆事务隔离级别问题-解决方案-MySQL session isolation level 'RE
    MySQLsessionisolationlevel'REPEATABLE-READ'isnolongersupported.Sessionisolationlevelmustbe'READ-COMMITTED'.Seehttp://confluence.atlassian.com/x/GAtmDg  成功解决方案:查看http://confluence.atlassian.com/x/GAtmDgFORMYSQL8.X......
  • 趣味解释Java虚拟机是啥玩意
    下文通过生动形象的例子,帮助小伙伴们轻轻松松地理解Java虚拟机的基本作用。大力:“为什么说Java语言是一种高级编程语言呢?”卫琴:“之所以称Java为高级语言,是因为它和人类的语言有一点点相近。比如用Employee类表示员工,用name属性表示员工的姓名,用selfIntro()方法模拟员工的自我介绍......
  • flask蓝图(这玩意就是django的子应用)
    蓝图的概念类似django的子应用,作用就是分模块开发,有关联的都放在一起。蓝图的创建步骤:新建一个包(一个包就是一个模块、等同于一个子应用)在包的__init__.py中创建蓝图对象。蓝图对象所有的参数和功能与Flask()对象类似。见:user下的__init__.py和views.py在app中注册蓝......
  • 发现的新玩意儿多客婚恋交友系统 / 新社交新新交友 / 同城交友同城相亲交友平台搭建
    系统分为2个版本:1、婚恋版:主要目的是婚恋,认证系统(实名认证、面部识别活体本人检测、学历证明、工资收入证明),搭载媒婆推广系统+红娘CRM管理系统+门店加盟系统、让征婚相亲不在难。2、交友版:主打交友聊天、语音房间、视频房间等功能。都具有完善的匹配算法和盈利模式。产品截......
  • 关于jsp借助WebServlet注解跳转到对应的servlet,表示界面404,且注解在前端界面不被识别
    问题描述我是属于那种习惯了使用其他框架之后,且,好久没有写过javaweb了,就忘记了jsp/html前端界面通过WebServlet注解跳转到servlet的方法,就这么一个破问题!!!坑了我一下午!!问题解决起初我还以为是servlet-api的依赖没有导入进去,发现早就在pom.xml文件里面好好地躺着了;当然,从始至终......