Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 深度搜索超时呀 有什么方法不会超时呀（附带代码）

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: