按时间一步一步模拟。
每一次,首先将所有没有水但是可以被灌到水的管子标记为有水,然后求出有水的管子里水面高度的最小值。
如果$a$号管有水且最小值为$b$,那么说明此时蜘蛛碰到了水。
如果有管子溢出且最小值就是它,那么说明此时无论如何水面都不会再上涨,即无解。
然后往所有高度等于最小值的管子里灌上一高度的水即可。
#include<cstdio>
const int N=25,M=110;
int n,m,i,j,x,y,z,A,B,T,g[N],v[M],w[M],nxt[M],ed;
struct P{int x,y,h,v;}a[N];
int getid(int x){for(int i=1;i<=n;i++)if(a[i].x==x)return i;}
void add(int x,int y,int z){
v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;
v[++ed]=x;w[ed]=z;nxt[ed]=g[y];g[y]=ed;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].h),a[i].h+=a[i].y,a[i].v=i==1;
scanf("%d",&m);
while(m--)scanf("%d%d%d",&x,&y,&z),add(getid(x-1),getid(x+z),y);
scanf("%d%d",&A,&B);
while(1){
for(x=1;x;)for(x=0,i=1;i<=n;i++)if(a[i].v)
for(j=g[i];j;j=nxt[j])if(a[i].h<=w[j]&&!a[v[j]].v)a[v[j]].v=x=1;
for(m=0,i=1;i<=n;i++)if(a[i].v&&a[i].h>m)m=a[i].h;
if(a[A].v&&m==B)return printf("%d",T),0;
for(i=1;i<=n;i++)if(a[i].v&&a[i].y==a[i].h&&a[i].y==m)return puts("-1"),0;
for(i=1;i<=n;i++)if(a[i].v&&a[i].h==m)a[i].h--,T++;
}
}
BZOJ1092 : [SCOI2003]蜘蛛难题的更多相关文章
-
【SCOI2003】【BZOJ1092】蜘蛛难题
有一堆管道,还有一个蜘蛛Willy,如下图所示.所有管道的是上端开口,下端封底,直径都是1cm,连接两个管道的连接容量无限,但体积可以忽略不计. 在第一个管道上方有一个水源,从中有水不断往下流,速度为 ...
-
[SCOI2003]蜘蛛难题
题目 对于当年来说似乎是神题?? 做法 对于联通注水来说,我们考虑把所有能平分到水的桶同时加高度,然后暴力判断 My complete code copy来的代码 #include <cstdi ...
-
bzoj AC倒序
Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem ...
-
探讨webapp的SEO难题(上)
前言 网络蜘蛛无法解析javascript,至少百度是不能的,神马搜索差的更远,而我们的webapp的渲染展示完全由javascript驱动 所以蜘蛛访问webapp页面会得到一个白页面,比如,我们期 ...
-
c#蜘蛛
C#写一个采集器 using System; using System.Collections.Generic; using System.Text; using System.Net; using ...
-
深入super,看Python如何解决钻石继承难题 【转】
原文地址 http://www.cnblogs.com/testview/p/4651198.html 1. Python的继承以及调用父类成员 python子类调用父类成员有2种方法,分别是普通 ...
-
判断来防ip是否为蜘蛛
判断网站来防IP是否为蜘蛛,用命令查询 : 一.在windows平台 蜘蛛反查命令:nslookup IP 点击"开始"-"运行"-"cmd& ...
-
BZOJ1090: [SCOI2003]字符串折叠
区间dp. 一种是分段dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); 一种是这一段可以缩写dp[i][j]=min(dp[i][j],dp[i][l]+2+ca ...
-
一起来做webgame,《Javascript蜘蛛纸牌》
不得不说,做游戏是会上瘾的,这次带来的是win系统上的经典游戏<蜘蛛纸牌>,不能完美,但求一玩 移牌 0 次 Javascript game_蜘蛛纸牌 正在努力加载... // " ...
随机推荐
-
WebApi防重复提交方案
使用Redis锁机制. 偽代碼: void post { var key = GetKey(); var value = Redis.Incre(key); if(value == 1) { var ...
-
别误用IsDigit与IsNumber函数(转)
1.起因 最近发现程序中有一段控制TextBox数字输入的代码,相信大家都不会太陌生,如下: void int_KeyPress(object sender, KeyPressEventArgs e) ...
-
MVC路由探寻,涉及路由的惯例、自定义片段变量、约束、生成链接和URL等
引子 在了解MVC路由之前,必须了解的概念是"片段".片段是指除主机名和查询字符串以外的.以"/"分隔的各个部分.比如,在http://site.com/Hom ...
-
2.mybatis入门实例 连接数据库进行查询
1.新建项目,添加mybatis和mysql的jar包 2.在mysql中新建表user[id,name,age] CREATE TABLE `users` ( `id` ) NOT NULL aut ...
-
图的最短路算法 Bellman-Ford
BF求图的最短路径的时间复杂度是O(MN),这样的时间复杂度并不比迪杰斯特拉算法好,但是BF算法支持图中存在负权的情况,但图中不能存在负圈,因为如果存在负圈,最短路是不存在的,因此BF算法的另一个重要 ...
-
css动画集合地址
CSS3 UI Lib库是由腾讯AlloyTeam前端开发团队建立,主要收集国内外友好体验和创意的界面组件Demo. 它除了使用CSS3技术外,还使用了HTML5,JS,JX,jQuery等技术,来达 ...
-
[Node.js] Web Scraping with Pagination and Advanced Selectors
When web scraping, you'll often want to get more than just one page of data. Xray supports paginatio ...
-
sql server DateTime相关内置函数总结
本文部分内容参考msdn帮助文档和博客园!汇总备忘 1.获取当前日期 getdate()函数以datetime数据类型的格式返回当前SQLServer服务器所在计算机的日期和时间.其语法格式 ...
-
python gui 之 tkinter库
http://blog.csdn.net/jcodeer?viewmode=contents http://tieba.baidu.com/p/3082739560 http://blog.sina. ...
-
斯坦福大学公开课机器学习:Neural network-model representation(神经网络模型及神经单元的理解)
神经网络是在模仿大脑中的神经元或者神经网络时发明的.因此,要解释如何表示模型假设,我们先来看单个神经元在大脑中是什么样的.如下图,我们的大脑中充满了神经元,神经元是大脑中的细胞,其中有两点值得我们注意 ...