The Preliminary Contest for ICPC Asia Nanjing 2019 - D Robots(概率dp+拓扑排序)
2024-09-06 23:21:15
这题概率dp + 拓扑排序可以写
改天补解释
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>vec[maxn];
int indeg[maxn],seq[maxn];
double d[maxn],f[maxn];
int N,M,T,tot=0;
void topo()
{
queue<int>q;
q.push(1);
tot=0;
seq[tot++]=1;
while (!q.empty()) {
int u=q.front();
q.pop();
for (int i=0;i<vec[u].size();i++) {
if (--indeg[vec[u][i]]==0) {
q.push(vec[u][i]);
seq[tot++]=vec[u][i];
}
}
}
}
int main()
{
scanf("%d",&T);
while (T--) {
scanf("%d%d",&N,&M);
for (int i=1;i<=N;i++) {
vec[i].clear();
}
memset(indeg,0,sizeof(indeg));
for (int i=0;i<=N;i++) {
d[i]=0;
f[i]=0;
}
int x,y;
for(int i=0;i<M;i++) {
scanf("%d%d",&x,&y);
vec[x].push_back(y);
indeg[y]++;
}
topo();
for (int i=tot-2;i>=0;i--) {
int u=seq[i];
int cnt=vec[u].size()+1;
for (int j=0;j<cnt-1;j++) {
d[u]+=d[vec[u][j]];
}
d[u]=(d[u]/(double)cnt+1)*(double)cnt/(double)(cnt-1);
}
for (int i=tot-2;i>=0;i--) {
int u=seq[i];
int cnt=vec[u].size()+1;
for (int j=0;j<cnt-1;j++) {
f[u]+=f[vec[u][j]];
}
f[u]+=cnt*d[u];
f[u]=f[u]/(double)(cnt-1);
}
printf("%.2lf\n",f[1]);
}
return 0;
}
最新文章
- Stanford NLP 学习笔记2:文本处理基础(text processing)
- Semantic UI – 完全语义化的前端界面开发框架
- remove() 方法的兼容问题
- Eclipse的常用快捷键、旁门左道、系统错误小贴士
- JavaScript 页面跳转的几种方式 转
- \r,\n,\t
- identifier not found error on function call
- MySQL show status详解
- 修改Android中strings.xml文件, 动态改变数据
- Android自定义View之音频条形图
- Vijos 1002 过河 状态压缩DP
- scrapy---callback 传递自定义参数
- Hexo博客搭建
- 简单配置umiJS学习笔记
- swift 警告框 - 自定义按钮颜色,图片
- C++max的使用方法
- F. Ivan and Burgers(线性基,离线)
- Mac iTerm2登陆CentOS提示warning: setlocale: LC_CTYPE: cannot change locale (UTF-8): No such file or directory
- P1757 通天之分组背包 / hdu1712 ACboy needs your help (分组背包入门)
- 我和C语言程序