[Luogu P5045] [BZOJ 1092] [SCOI2003]蜘蛛难题

洛谷传送门

BZOJ传送门

题目描述

有一堆管道，还有一个蜘蛛$\text{Willy}$Willy，如下图所示。所有管道的是上端开口，下端封底，直径都是$1cm$1cm，连接两个管道的连接容量无限，但体积可以忽略不计。

在第一个管道上方有一个水源，从中有水不断往下流，速度为每秒$0.25cm^3$0.25cm3。由于管道横截面积为$0.25cm^2$0.25cm2，所以单给一个管道注水时水面每秒上升$1cm$1cm。根据物理知识，在前$2$2秒中，水注如左边的管道底部，第$[3,5]$[3,5]秒时注入右边的管道，第$[6,9]$[6,9]秒同时注入两个管道（虽然流量不变，但是由于同时给两个管道注水，因此水面上升的速度仅为每秒$0.5cm$0.5cm），接触到蜘蛛。 给出管道和管道之间连接的位置，以及蜘蛛$\text{Willy}$Willy的位置，求水面接触到$\text{Willy}$Willy的时间。假设蜘蛛的实际位置比给出的略高一点，因此如果蜘蛛在左边管道的$n=4$n=4的位置，答案应该是$5$5秒。因为前两秒后水面虽然看起来接触到了$\text{Willy}$Willy，但实际上比$\text{Willy}$Willy略低一点。

输入输出格式

输入格式：

所有位置都用有序数对$(x, y)$(x,y)表示，其中$y$y坐标从上到下逐渐增大；$x$x坐标从左到右逐渐增大，因此左上角的坐标为$(0,0)$(0,0)，其他所有坐标值为$0$0到$100$100之间的整数。输入第一行为一个整数$p(1\le p\le 20)$p(1≤p≤20)，表示管道的数目；以下$p$p行，每行用$x, y, h$x,y,h三个整数描述一根管道。$(x,y)$(x,y)为管道左上角坐标；$h$h为管道高度$(1\le h\le 20)$(1≤h≤20)。以下一行为一个整数$L(0\le L\le 50)$L(0≤L≤50)，为连接的个数。

以下$L$L行每行用三个整数$x, y, d$x,y,d描述一个连接，$(x,y)$(x,y)为左端点的坐标，$d$d为连接的长度$(1\le d\le 20)$(1≤d≤20)。最后一行为两个整数$a,b$a,b，表示$\text{Willy}$Willy在管道$a$a的$y$y坐标为$b$b的位置。管道按照在文件中出现的顺序编号为$1,2,3…p$1,2,3…p

以下为一些假设： 水源总是在第一根管道的正上方, 连接不会穿越管道,任意两个连接的$y$y坐标都不相同,任意两个管道的左上角的$x$x坐标都不相同,任意连接的两个端点都在管道上（不会出现悬空的情形）

输出格式：

仅一个整数，为水面接触到$\text{Willy}$Willy的时间。如果水面无法接触到$\text{Willy}$Willy，输出$-1$−1。

输入输出样例

输入样例#1：

2
2 0 6
5 1 6
1
3 4 2
2 2

输出样例#1：

9

解题分析

模拟一下， 维护当前水能灌到的最低的位置， 然后使其水位上升$1cm$1cm。 如果某次水溢出了容器而还没到达蜘蛛的位置就输出$-1$−1。

代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define MX 105
#define gc getchar()
#define ll long long
template <class T>
IN void in(T &x)
{
	x = 0; R char c = gc;
	for (; !isdigit(c); c = gc);
	for (;  isdigit(c); c = gc)
	x = (x << 1) + (x << 3) + c - 48;
}
template <class T> IN T max(T a, T b) {return a > b ? a : b;}
template <class T> IN T min(T a, T b) {return a < b ? a : b;}
int n, m, x, y, cnt;
int head[MX];
bool wat[MX];
struct Pipe {int x, up, down;} pip[MX];
struct Edge {int to, dep, nex;} edge[MX];
IN void add(R int from, R int to, R int dep)
{
	edge[++cnt] = {to, dep, head[from]}, head[from] = cnt;
	edge[++cnt] = {from, dep, head[to]}, head[to] = cnt; 
}
IN int find(R int x)
{
	for (R int i = 1; i <= n; ++i)
	if (pip[i].x == x) return i;
	return 0;
}
int main(void)
{
	in(n); int l, len, p;
	for (R int i = 1; i <= n; ++i)
	in(pip[i].x), in(pip[i].up), in(pip[i].down), pip[i].down += pip[i].up;
	in(m);
	for (R int i = 1; i <= m; ++i)
	{
		in(l), in(p), in(len);
		add(find(l - 1), find(l + len), p);
	}
	in(x), in(y); wat[1] = true; int ans = 0;
	W (233)
	{
		bool nex = true;
		W (nex)
		{
			nex = false;
			for (R int i = 1; i <= n; ++i)
			{
				if (wat[i])
				{
					for (R int j = head[i]; j; j = edge[j].nex)
					{
						if ((!wat[edge[j].to]) && edge[j].dep >= pip[i].down)
						wat[edge[j].to] = nex = true;
					}
				}
			}
		}
		int mxdp = 0;
		for (R int i = 1; i <= n; ++i) if (wat[i]) mxdp = max(mxdp, pip[i].down);
		if (wat[x] && mxdp == y) return printf("%d\n", ans), 0;
		for (R int i = 1; i <= n; ++i)
		{
			if (wat[i] && pip[i].down == mxdp)
			{
				if (pip[i].down == pip[i].up) return puts("-1"), 0;
				++ans, pip[i].down--;
			}
		}
	}
}