 /**//*
题意: 给出一些相连的管,从第一个管开始注水,问到达管ID的Y的时间
No two links have the same y coordinates.
所以最多一个pipe到另一个pipe
a->b,而当b升到跟a一样高时,两者一起升
利用这点,可以用一个栈保存现场!

当level升到某一个link的高度时,就传给另一个pipe k了,更新level = py[k]+ph[k],这时管数目为1
(当然可以继续传给k',用栈记录即可)
而再次回到这个高度时,pop栈,一起升了,total+=栈顶

即:传播开+回来一起升 Like Stack
*/
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

int px[21],py[21],ph[21],pNum;
int lxl[51],lxr[51],ly[51],lNum;
bool water[21];

int main()
  {
//freopen("in","r",stdin);
int T,Y,ID;
scanf("%d",&T);
while(T--)
 {
scanf("%d",&pNum);
for(int i=1;i<=pNum;i++)
scanf("%d%d%d",&px[i],&py[i],&ph[i]);
scanf("%d",&lNum);
for(int i=1;i<=lNum;i++)
 {
scanf("%d%d%d",&lxl[i],&ly[i],&lxr[i]);
lxr[i]+=lxl[i]--;
}
scanf("%d%d",&ID,&Y);
if(Y<=py[ID]||Y>py[ID]+ph[ID])//注意这种情况!
 {
puts("No Solution");
continue;
}
bool ns=0,New;
int time=0,level=py[1]+ph[1],total=1,overflow=py[1];
memset(water,0,sizeof(water));
water[1]=1;
vector<pair<int,int> >S;
while(true)
 {
New = 0;
for(int i=1;i<=lNum;i++)
 {
if(ly[i]==level)
 {
for(int j=1;j<=pNum;j++)
 {
if(water[j])
 {
int k;
for(k=1;k<=pNum;k++)
 {
if(lxl[i]==px[j]&&lxr[i]==px[k]||lxl[i]==px[k]&&lxr[i]==px[j])
 {
if(!water[k])//new
 {
S.push_back(make_pair(total,j));
level=py[k]+ph[k];
if(overflow<py[k])overflow=py[k];
total=1;
water[k]=1;
New = 1;
}
else
 {
if(S.size()&&(S[S.size()-1].second==j||S[S.size()-1].second==k))//pop and back
 {
total += S[S.size()-1].first;
//printf("%d %d %d\n",j,k,total);
S.pop_back();
}
}
break;//find out ,so break
}
}
if(k<=pNum)break;
}
}
break;//only one link = level (No two links have the same y coordinates.)
}
}
if(New)continue;
if(level<=overflow||Y<=overflow)//
 {
ns=1;
break;
}
if(level<=Y&&water[ID])break;
level--;
time+=total;
}
if(ns)puts("No Solution");
else printf("%d\n",time);
}
return 0;
}
 /**//*
Test

2
0 0 3
2 3 1
1
1 3 1
1 3

7
10 4 6
7 0 13
12 0 13
3 2 8
0 7 6
1 0 6
5 5 7
13
2 1 5
2 3 1
1 9 2
1 12 4
4 8 1
11 10 1
8 13 4
8 2 4
4 4 3
8 5 2
4 6 1
6 7 1
6 11 1
7 12

*/
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|