codeforce Gym 100685F Flood (topo排序)
2024-09-08 17:18:43
如果直接模拟水向周围流会TLE,因为某些个结点被重复扩展了多次,
科学做法是topo排序,每次只把入度为0的点放入队列,这样就严格保证了每个结点只被扩展一次。
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-9
#define bug(x) cout<<#x<<'='<<x<<endl;
#define Min 1e-7
const int maxn = 1e4+;
const int maxe = 1e5+; struct Ponds
{
double cap,now;
}; typedef Ponds Pants; Pants P[maxn];
int N,K; vector<int> son[maxn]; int St,Tar,Amount;
int in[maxn];
queue<int> q; void topo()
{ P[St].now += Amount;
q.push(St);
for(int i = ; i <= N; i++) if(!in[i] && i!= St) q.push(i); while(q.size()){
int u = q.front(); q.pop();
Pants &p = P[u];
if(p.now - p.cap > ){
if(son[u].size()){
double each = (p.now-p.cap)/son[u].size();
p.now = p.cap;
for(int i = ; i < son[u].size(); i++){
int v = son[u][i];
P[v].now += each;
if(--in[v] == ) q.push(v);
}
}else {
p.now = p.cap;
}
} } }
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&N,&K);
for(int i = ; i <= N; i++){
scanf("%lf%lf",&P[i].cap,&P[i].now);
}
for(int i = ; i < K; i++){
int u,v; scanf("%d%d",&u,&v);
son[u].push_back(v);
in[v]++;
} scanf("%d%d%d",&St,&Amount,&Tar); topo();
printf("%lf",P[Tar].now);
return ;
}
最新文章
- Spring的三种通过XML实现DataSource注入方式
- JavaScript的几种Math函数,random(),ceil(),round(),floor()
- PowerDesigner中Name与Code同步的问题
- backtrack下vim的使用
- MathType的公式在word中跟文字不对齐
- [moka同学摘录]Yii2.0开发初学者必看
- C++问题-无法打开包括文件:“GLES2/gl2.h”
- ADN中国团队參加微软的Kinect全国大赛获得三等奖
- ios 控件 UIButton
- ASP.NET Core托管和部署Linux实操演练手册
- oracle 18c centos7 设置开机自动启动Oracle
- Java安全通信:HTTPS与SSL
- 20145118 《Java程序设计》 实验报告三
- STL中set和map
- Fluent Nhibernate Mapping for Sql Views
- Linux命令:chmod、chgrp、chown的区别
- 流Stream 文件File 流IO
- C#工具类之素数扩展类
- js模板方法
- Java使用apache的开源数据处理框架commons-dbutils完成查询结果集的各种处理输出(8种方式)