Gym - 100685F

题意:n个水池之间流水,溢出多少流出多少,多个流出通道的话平均分配,给你每个水池中的水量和容量,问到最后目标水池中水量。

思路:直接用队列扩展,不过这里有一个优化,就是统计一下每个点的入度,只有对一个点访问次数达到入度次了,再将其加入队尾,这样就保证了对每个点只操作一次,不然WA、TLE各种错

 #pragma comment(linker, "/STACK:1000000000")
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 0x3f3f3f3f
#define MAXN 100005
#define MAXK 100005
#define eps 1e-8
using namespace std;
struct Node{
double m, now;
};
Node p[MAXK];
int cnt[MAXK];
vector<int> G[MAXK];
queue<int> Q;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // OPEN_FILE
int n, k;
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++){
scanf("%lf%lf", &p[i].m, &p[i].now);
//p[i].pos = i;
}
int x, y, z;
//double y;
memset(cnt, , sizeof(cnt));
for(int i = ; i <= k; i++){
scanf("%d%d", &x, &z);
G[x].push_back(z);
cnt[z]++;
}
scanf("%d%d%d", &x, &y, &z);
// int head = 1, tail = 1;
p[x].now += y;
Q.push(x);
//vis[x] = true;
//double ans = p[z].now;
//int cnt = 0;
while(!Q.empty()){
//cnt++;
int pos = Q.front();
Q.pop();
Node q = p[pos];
if(q.now <= q.m) continue;
p[pos].now = p[pos].m;
if(G[pos].size() == ) continue;
double u = (q.now - q.m) / G[pos].size();
for(int i = ; i < G[pos].size(); i++){
//if(vis[G[q.pos][i]]) continue;
p[G[pos][i]].now += u;
//tail++;
cnt[G[pos][i]]--;
if(cnt[G[pos][i]] == ){
Q.push(G[pos][i]);
}
}
}
printf("%.6lf\n", p[z].now);
}

最新文章

  1. 学习微信小程序之css8
  2. 压力测试相关之ab命令
  3. org.apache.jasper.JasperException:省略&quot;/html/sysmaintain/authority/user/../../module/verify_login.jsp&quot; not found
  4. 【译】.NET中六个重要的概念:栈、堆、值类型、引用类型、装箱和拆箱
  5. Javascript常用对象的属性和方法
  6. JS控制图片显示的大小(图片等比例缩放)
  7. hiho #1114 : 小Hi小Ho的惊天大作战:扫雷&#183;一
  8. Spark Tungsten揭秘 Day1 jvm下的性能优化
  9. Redis 和 Memcached 的区别
  10. 使用Eclipse调试Android Native Application---cocos2d-x + Eclipse + Android + ndk
  11. nginx + lua 构建网站防护waf(一)
  12. CDLinux环境下WiFi密码破解
  13. 人生新开始&mdash;&mdash;第一天上班
  14. Matlab Error (Matrix dimensions must agree)
  15. 【20190328】CSS-transform-origin(变形原点)解析
  16. FFmpeg Android 学习(一):Android 如何调用 FFMPEG 编辑音视频
  17. 写一个ORM框架的第一步(Apache Commons DbUtils)
  18. IDEA中更改Tomcat服务器的URL
  19. H5、React Native、Native性能区别选择
  20. Hausdorff Distance(豪斯多夫距离)

热门文章

  1. 带入gRPC:gRPC Deadlines
  2. vue非父子组件间传参问题
  3. 洛谷 P1855 榨取kkksc03 (二维费用背包)
  4. React 使用link在url添加参数(url中不可见)
  5. Java基础学习总结(30)——Java 内存溢出问题总结
  6. [terry笔记]redhat5.5_11gR2_RAC_安装
  7. spring揭秘 读书笔记 二 BeanFactory的对象注冊与依赖绑定
  8. POJ 2516 Minimum Cost (最小费用最大流)
  9. 手动配置三大框架整合:Spring+Struts2+mybatis
  10. 设置Webdriver启动chrome为默认用户的配置信息