 /**//*
題意: 給出一些相連的管,從第一個(gè)管開(kāi)始注水,問(wèn)到達(dá)管ID的Y的時(shí)間
No two links have the same y coordinates.
所以最多一個(gè)pipe到另一個(gè)pipe
a->b,而當(dāng)b升到跟a一樣高時(shí),兩者一起升
利用這點(diǎn),可以用一個(gè)棧保存現(xiàn)場(chǎng)!

當(dāng)level升到某一個(gè)link的高度時(shí),就傳給另一個(gè)pipe k了,更新level = py[k]+ph[k],這時(shí)管數(shù)目為1
(當(dāng)然可以繼續(xù)傳給k',用棧記錄即可)
而再次回到這個(gè)高度時(shí),pop棧,一起升了,total+=棧頂

即:傳播開(kāi)+回來(lái)一起升 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
搜索
最新評(píng)論

|
|