Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 411 Solved: 159
Description
有一堆管道，还有一个蜘蛛Willy，如下图所示。所有管道的是上端开口，下端封底，直径都是1cm，连接两个管道的连接容量无限，但体积可以忽略不计。
在第一个管道上方有一个水源，从中有水不断往下流，速度为每秒0.25 cm3。由于管道横截面积为0.25 cm3，所以单给一个管道注水时水面每秒上升1cm。根据物理知识，在前2秒中，水注如左边的管道底部，第3~5秒时注入右边的管道，第6~9秒同时注入两个管道（虽然流量不变，但是由于同时给两个管道注水，因此水面上升的速度仅为每秒0.5cm），接触到蜘蛛。 给出管道和管道之间连接的位置，以及蜘蛛Willy的位置，求水面接触到Willy的时间。假设蜘蛛的实际位置比给出的略高一点，因此如果蜘蛛在左边管道的n=4的位置，答案应该是5秒。因为前两秒后水面虽然看起来接触到了Willy，但实际上比Willy略低一点。
Input
所有位置都用有序数对(x, y)表示，其中y坐标从上到下逐渐增大；x坐标从左到右逐渐增大，因此左上角的坐标为(0,0)，其他所有坐标值为0到100之间的整数。输入第一行为一个整数p(1<=p<=20)，表示管道的数目；以下p行，每行用x, y, h三个整数描述一根管道。(x,y)为管道左上角坐标；h为管道高度(1<=h<=20)。以下一行为一个整数L(0<=L<=50)，为连接的个数。以下L行每行用三个整数x, y, d描述一个连接，(x,y)为左端点的坐标，d为连接的长度(1<=d<=20)。最后一行为两个整数a, b，表示Willy在管道a的y坐标为b的位置。管道按照在文件中出现的顺序编号为1,2,3…p 以下为一些假设： 水源总是在第一根管道的正上方 连接不会穿越管道 任意两个连接的y坐标都不相同 任意两个管道的左上角的x坐标都不相同 任意连接的两个端点都在管道上（不会出现悬空的情形）
Output
仅一个整数，为水面接触到Willy的时间。如果水面无法接触到Willy，输出-1。
Sample Input
2
2 0 6
5 1 6
1
3 4 2
2 2
Sample Output
9
HINT
该样例对应题目中的例子。
/**************************************************************
Problem: 1092
User: ictsing
Language: C++
Result: Accepted
Time:4 ms
Memory:1296 kb
****************************************************************/
//BZOJ1092 [SCOI2003]蜘蛛难题
#include <iostream>
#include <cstdio>
using namespace std;
const int mt = 25,mm=100+5;
int ecnt=0;
int adj[mt],to[mm<<1],nxt[mm<<1],w[mm<<1];
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
struct point
{
int x,y,h,v;
}a[mt];
int _clock=0;
int n;
int getid(int x)
{
for(int i=1;i<=n;i++)
if(a[i].x==x) return i;
return 0;
}
void adde(int u,int v,int ww)
{
ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],w[ecnt]=ww,adj[u]=ecnt;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i].x=read(),a[i].y=read(),a[i].h=a[i].y+read(),a[i].v=i==1;
int m=read();
while(m--)
{
int x=read(),y=read(),z=read();
adde(getid(x-1),getid(x+z),y);
adde(getid(x+z),getid(x-1),y);
}
int aa=read(),bb=read();
while(true)
{
bool flag=1;
while(flag)
{
flag=false;
for(int i=1;i<=n;i++)
{
if(a[i].v)
for(int j=adj[i];j;j=nxt[j])
{
int v=to[j];
if(a[i].h<=w[j]&&!a[v].v)
a[v].v=1,flag=true;
}
};
}
int maxx=0;
for(int i=1;i<=n;i++)
if(a[i].v)
maxx=max(maxx,a[i].h);
if(a[aa].v&&maxx==bb)
{
printf("%d",_clock);
return 0;
}
for(int i=1;i<=n;i++)
{
if(a[i].v&&a[i].y==a[i].h&&a[i].y==maxx)
{
puts("-1");
return 0;
}
}
for(int i=1;i<=n;i++)
if(a[i].v&&a[i].h==maxx)
a[i].h--,_clock++;
}
return 0;
}
评论