如果直接模拟水向周围流会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 ;
}

最新文章

  1. Spring的三种通过XML实现DataSource注入方式
  2. JavaScript的几种Math函数,random(),ceil(),round(),floor()
  3. PowerDesigner中Name与Code同步的问题
  4. backtrack下vim的使用
  5. MathType的公式在word中跟文字不对齐
  6. [moka同学摘录]Yii2.0开发初学者必看
  7. C++问题-无法打开包括文件:“GLES2/gl2.h”
  8. ADN中国团队參加微软的Kinect全国大赛获得三等奖
  9. ios 控件 UIButton
  10. ASP.NET Core托管和部署Linux实操演练手册
  11. oracle 18c centos7 设置开机自动启动Oracle
  12. Java安全通信:HTTPS与SSL
  13. 20145118 《Java程序设计》 实验报告三
  14. STL中set和map
  15. Fluent Nhibernate Mapping for Sql Views
  16. Linux命令:chmod、chgrp、chown的区别
  17. 流Stream 文件File 流IO
  18. C#工具类之素数扩展类
  19. js模板方法
  20. Java使用apache的开源数据处理框架commons-dbutils完成查询结果集的各种处理输出(8种方式)

热门文章

  1. BootStrap 概念
  2. HDU 5546 Ancient Go (搜索)
  3. unity3d 自定义载入条/载入动画
  4. 【转】oracle的分析函数over
  5. 聊聊 Laravel 5.5 的 「自动发现」
  6. Eclipse集成Git的实践
  7. 填坑帖 By cellur925
  8. DOM的学习网站 DOM是HTML和XML的编程接口
  9. JavaScript进阶 - 第6章 事件响应,让网页交互
  10. vue教程4-vueadmin上手