/**//* 题意: 给出一些相连的管,从第一个管开始注水,问到达管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
搜索
最新评论
|
|