这道题最难的地方是当一种药和它的一个后续药品出现后，如何防止其他的后续药品在搜索中出现，因为搜索的时候是按位置顺序探测的，所以位置不是相邻的时候，从下一层回退回来并不知道前面已经有这样的状态。剪枝的条件应该还有，我这个代码还是很慢。
测试用例：
输入：
复制代码
5
2 4 5
1 3
5
2 3
1 2 4
4
0
3
0
0
复制代码
输出：
2
2 3 5 4
4 3 5 1
复制代码
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int MAXSIZE = 500;//最大药品数目
vector<vector<int> > medicVect;//记录每种药品的后续药
vector<vector<int> >answers;//记录搜索到的所有药方
vector<int> target;//当前药方
vector<int> answer;//当前解法
int n,p,nCount;
bool used[MAXSIZE];//药是否已经出现
int limit[MAXSIZE];//若药品及其后续药出现了，则限制其他后续药再次出现
bool is_Succ(int x,int y)
{//判断y是不是x的后续药
bool result = false;
int i;
for (i=0;i<medicVect[x].size();++i)
{
if (medicVect[x][i]==y)
{
result = true;
}
}
return result;
}
int is_one_pred(int x)
{//取x的唯一前驱药,若为则说明前驱药不唯一
int result = 0;
int i,k;
k = 0;
for (i=0;i<n;++i)
{
if (is_Succ(i,x)==true)
{
if (k==0)
{
k = i;
}
else
{
return result;
}
}
}
result = k;
return result;
}
void limit_inc(int x)
{//把x的后续药都标记为不可以再使用
int i;
for (i=0;i<medicVect[x].size();++i)
{
++limit[medicVect[x][i]];
}
}
void limit_dec(int x)
{//撤销x后续药不可以再使用的标记
int i;
for (i=0;i<medicVect[x].size();++i)
{
--limit[medicVect[x][i]];
}
}
bool init()
{
nCount = 0;//解法数
answer.resize(p+1);
answer[0] = 0;
int i,j,k;
//初始化限制条件，值均为
for (i=0;i<MAXSIZE;++i)
{
limit[i] = 0;
}
for (i=2;i<=p-1;++i)
{
if (target[i]!=0)
{
//若有唯一的前驱药，则后续药不得再次出现，否则无解
k = is_one_pred(target[i]);
if (k==0)continue;
for (j=i+1;j<=p;++j)
{
if(is_Succ(k,target[j]))
return false;
}
}
}
//记录已经知道的药(被使用了，可不参与搜索)
for (i=1;i<=p;++i)
{
if (target[i]!=0)
{
used[target[i]] = true;
}
}
return true;
}
void Solve(int curPos)
{
int i,num;
if (curPos>p)
{//找到一种解
//输出一个解法
answers.push_back(answer);//保存当前解法
nCount++;//解法数加
return;
}
if (target[curPos]==0)
{//当前位置药品未知,从前一药品的后续药中进行试探
for (i=0;i<medicVect[answer[curPos-1]].size();++i)
{
num = medicVect[answer[curPos-1]][i];
if (used[num]==false && limit[num]==0)
{//符合条件,放置药品下去
if (curPos>1)
{//设置限制条件,防止后续药品出现
limit_inc(answer[curPos-1]);
}
answer[curPos] = num;//放入解法中
used[num] = true;//被使用了
Solve(curPos+1);//进入下一个位置的试探
used[num] = false;//从上一层回来，重置状态
if (curPos>1)
{//恢复到原来的限制条件
limit_dec(answer[curPos-1]);
}
}
}
}
else
{//第curPos个位置的药已知
if (curPos>1)
{
if (target[curPos-1]==0)
{//判断是否满足前后继的关系
if (!is_Succ(answer[curPos-1],target[curPos]))
{
return;
}
}
}
if (curPos>1)
{//设置限制条件,防止后续药品出现
limit_inc(answer[curPos-1]);
}
answer[curPos] = target[curPos];//放入解法中
Solve(curPos+1);//进入下一个位置的试探
if (curPos>1)
{//恢复到原来的限制条件
limit_dec(answer[curPos-1]);
}
}
}
int main()
{
int i,num;
cin>>n;
string input;
getline(cin,input);
//任何药都是号药的后续药
vector<int> firstVect;
for (i=0;i<n;++i)
{
firstVect.push_back(i+1);
}
medicVect.push_back(firstVect);
//输入每一种药品的后续药
for (i=0;i<n;++i)
{
vector<int> tmpVect;
getline(cin,input);
string::iterator pos = input.begin();
do
{
string temp;
pos = find(input.begin(),input.end(),' ');//找到分隔符
copy(input.begin(),pos,back_inserter(temp));
num = atoi(temp.c_str());
tmpVect.push_back(num);
if (pos==input.end())
{//最后一个数字了
break;
}
else
{
input.erase(input.begin(),++pos);
}
} while (pos!=input.end());
medicVect.push_back(tmpVect);
}
//输入给定的药方
cin>>p;
target.resize(p+1);
for (i=1;i<=p;++i)
{
cin>>num;
target[i] = num;
}
if (!init())
{//无解
cout<<"解法数目: "<<nCount<<endl;
}
else
{
Solve(1);
cout<<nCount<<endl;
vector<vector<int> >::iterator iter;
for (iter = answers.begin();iter!=answers.end();++iter)
{
int size = iter->size();
for (i = 1;i<size;++i)
{
cout<<(*iter)[i]<<" ";
}
cout<<endl;
}
}
system("pause");
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/11/18/1336080.html，如需转载请自行联系原作者
