Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

深度搜索超时呀 有什么方法不会超时呀(附带代码)

Posted by qqyukuilong at 2009-10-17 08:00:13 on Problem 2303
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
struct doll
{
       int h,d,w;
       int outV,in_h,in_d;//doll的外部体积,内部高度,内部直径 
       doll(){h=0,d=0,w=0,outV=0,in_h=0,in_d=0;}
};
class Russian_Dolls
{
      public:
             bool input();
             void slove();         //解决问题 
      private:
             void output();
             bool DPS(int v,int n);//深度搜索 
             void Great();         //建立关系图 
             vector<int*> group;   //2维数组存储关系图 
             vector<doll> num;     //doll的数据 
             vector<int> visited;  //标记该节点是否以搜索 
             int size_doll;        //doll的总数 
             int size;             //每一组doll的个数  
};
bool cmp(doll  a,doll  b)
{
     return (a.outV>b.outV);
}
void Russian_Dolls::Great()
{
     int i,j;
     for(i=0;i<size_doll;i++)
     {
         for(j=i+1;j<size_doll;j++)
             if(num[i].in_h>=num[j].h&&num[i].in_d>=num[j].d)
                group[i][j]=1;
     }
}
bool Russian_Dolls::input()
{
     int i,n;
     doll t;
     scanf("%d",&n);
     size_doll=n*2;
     size=n;
     if(size_doll==0)return false;
     num.assign(size_doll,t);
     visited.assign(size_doll,0);
     for(i=0;i<size_doll;i++)
     {
          scanf("%d%d%d",&num[i].h,&num[i].d,&num[i].w);
          num[i].in_h=num[i].h-2*num[i].w;
          num[i].in_d=num[i].d-2*num[i].w;
          num[i].outV=num[i].d*num[i].d*num[i].h;
     }
     sort(num.begin(),num.end(),cmp);
     return true;
}
void Russian_Dolls::output()
{
     int i;
     for(i=0;i<size_doll;i++)
     {
         if(visited[i]==1)
		   printf("%d %d %d\n",num[i].h,num[i].d,num[i].w);
     }
     printf("-\n");
     for(i=0;i<size_doll;i++)
     {
         if(visited[i]==0)
			printf("%d %d %d\n",num[i].h,num[i].d,num[i].w);
     }
	 printf("\n");
}
bool Russian_Dolls::DPS(int v,int count)
{
     if(count==0)
     {   
		 visited[v]=1;
         output();
         return true;
     }
     else
     {
         for(int i=v+1;i<size_doll;i++)
         {
                 if(count==size_doll-v-1)
                 {
                      for(int j=i-1;j<size_doll;j++)visited[j]=1;
                      output();
                      return true;
                 }
               /*  if(count>size_doll-v-1)
				 {
					 return false;
				 }*/
                 visited[v]=1;
                 if(!visited[i]&&group[v][i])
                 {
                       if(DPS(i,count-1))return true;
                       visited[i]=0;
                 }    
                 
         }
     }
     return false;
}
void Russian_Dolls::slove()
{
     int i,j;
     group.assign(size_doll,(int*)NULL);
     for(i=0;i<size_doll;i++)
        group[i]=new int[size_doll];
     for(i=0;i<size_doll;i++)
        for(j=0;j<size_doll;j++)
            group[i][j]=0;
     Great();
     DPS(0,size-1);
     for(i=0;i<size_doll;i++)
         delete [] group[i];
     group.clear();
     visited.clear();
     num.clear();
}
int main()
{
	while(1)
	{
	    Russian_Dolls bb;
            if(!bb.input())return 0;
            bb.slove();
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator