 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这个题用DFS确实是可以过的,但是用DFS过只不过是运气好罢了,最好的算法不是搜索,是图论最短路In Reply To:哪位大侠过了的帮忙看看 Posted by:arcane at 2005-08-03 11:28:50 > 我用深搜＋剪枝怎么还limited time exceed？哪位大侠帮忙看看（随手写的，很乱，呵呵）
> #include<iostream.h>
> #include<math.h>
> #include<stack>
> using namespace std;
> struct subnod{
> int nextnode;
> int cheaperprice;
> subnod *nextsub;
> };
> struct node{
> int price;
> int level;
> int numofsub;
> subnod *firstsub;
> };
> node nodearray[101];
> inline bool test(stack<subnod*> &a,int m,int d)
> {int maxlev=d;
> int minlev=d;
> subnod *b;
> stack<subnod*> c;
> while(a.empty()==false)
> {b=a.top();
> a.pop();
> c.push(b);
> if(nodearray[b->nextnode].level>maxlev)
> maxlev=nodearray[b->nextnode].level;
> if(nodearray[b->nextnode].level<minlev)
> minlev=nodearray[b->nextnode].level;
> }
> while(!c.empty())
> {b=c.top();
> c.pop();
> a.push(b);
> }
> if((maxlev-minlev)>m)
> return false;
> return true;
> }
>
> void main()
> {int M;
> int N;
> cin>>M;
> cin>>N;
> if(N<0||N>100)
> return;
> int i=1;
> int j=1;
> subnod *temp;
> subnod *tempnext;
> for(;i<=N;i++)
> {cin>>nodearray[i].price;
> cin>>nodearray[i].level;
> cin>>nodearray[i].numofsub;
> if(nodearray[i].numofsub!=0)
> nodearray[i].firstsub=new subnod;
> else nodearray[i].firstsub=NULL;
> temp=nodearray[i].firstsub;
> for(j=1;j<=nodearray[i].numofsub;j++)
> {cin>>temp->nextnode;
> cin>>temp->cheaperprice;
> if(j==nodearray[i].numofsub)
> tempnext=NULL;
> else
> tempnext=new subnod;
> temp->nextsub=tempnext;
> temp=tempnext;
> }
> }
> int tempprice=0;
> int tempmin=nodearray[1].price;
> int max=nodearray[1].level;
> stack<subnod*> astack;
> if((temp=nodearray[1].firstsub)!=NULL)
> {astack.push(temp);
> while(temp!=NULL)
> {if(test(astack,M,max))
> {tempprice+=(temp->cheaperprice);
> if(tempprice+nodearray[temp->nextnode].price<tempmin)
> tempmin=tempprice+nodearray[temp->nextnode].price;
> temp=nodearray[temp->nextnode].firstsub;
> if(temp!=NULL&&tempprice<tempmin)
> astack.push(temp);
> else
> while(temp==NULL)
> { if(!astack.empty())
> {
> temp=astack.top();
> astack.pop();
> tempprice-=temp->cheaperprice;
> temp=temp->nextsub;
> if(temp!=NULL)
> astack.push(temp);
> }
> else
> {cout<<tempmin;
> return;
> }
> }
> }
> else
> {astack.pop();
> temp=temp->nextsub;
> if(temp!=NULL&&tempprice<tempmin)
> astack.push(temp);
> else
> while(temp==NULL)
> { if(!astack.empty())
> {
> temp=astack.top();
> astack.pop();
> tempprice-=temp->cheaperprice;
> temp=temp->nextsub;
> if(temp!=NULL)
> astack.push(temp);
> }
> else
> {cout<<tempmin;
> return;
> }
> }
> }
> }
> }
> cout<<tempmin;
> }
>
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
