题解 P1171 【售货员的难题】
有一天一个蒟蒻，点了搜索标签。。。
进入售货员的难题
水了一发搜索，拿了80分QWQ
#include<cstdio>
using namespace std;
int lxy[21][21],hrb[21],n,i,j,k,minn=1e9;
int ss(int x,int y,int z)//x表示村子编号，y表示走了几个村子，z表示用到时间。。。
{
if(z>minn)return 0;//基本最小值剪枝
if(y==n&&z+lxy[x][1]<minn)
{minn=z+lxy[x][1];return 0;}//比较求最小值，其中的加lxy[x][1]意思是走回第一个村
for(int i=2;i<=n;i++)//循环开始
if(hrb[i]==0&&i!=x)//深搜模板，没走就搜
{
hrb[i]=1;//打点
ss(i,y+1,z+lxy[x][i]);
hrb[i]=0;//回溯
}
return 0;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
for(k=1;k<=n;k++)
scanf("%d",&lxy[i][k]);//输入
ss(1,1,0);//开搜
printf("%d",minn);
}交完后。。。
我想：这题暴力分给的好足啊。。。
于是flag：我今天就是从这跳下去，也不看一篇题解！
接着一波优秀的预判剪枝
然而还是只有90分（在100分代码了会讲）t10有多坑啊
1h后。。。我点开了题解。。。
woc这都啥玩意？？？
这题不搜索吗？题解咋全是dp状压QAQ
我不会写啊，我只会搜索QAQ
好吧！只能靠自己了QWQ
之后我想了一下
出题人一定会在后面卡人
So struct存图排序是个不错的想法，于是有了100分代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct pd{int ha,e;}lxy[25][25];
//存图，ha表示各点时间消耗，e表示要去的点，因为排序动列，不动行，所以记下列，就是要去的点
int hrb[25],n,i,j,k,minn=1e9,maxn=1001,emm[25];//新增一个emm数组解决排序动列的问题
int cmp(pd a,pd b){return a.ha<b.ha;}//排序函数
int ss(int x,int y,int z)
{
if(z>=minn)return 0;//用sort优化，提前找出最小值，剪枝
if(z+n-y+1+maxn>=minn)return 0；
//预见性剪枝，maxn表示x点到1的最小距离，然后剩余点取最小值1，极值判定
if(y==n){minn=min(minn,z+emm[x]);return 0;}
if(y<n)
for(int i=2;i<=n;i++)
if(hrb[lxy[x][i].e]==0)
//判断是否走过，为啥是lxy[x][i].e,请见上面解释
{
if(z+lxy[x][i].ha+n-y+maxn>minn)return 0;
//预见性剪枝，极值判定，用这两个可以90分
hrb[lxy[x][i].e]=1;
ss(lxy[x][i].e,y+1,z+lxy[x][i].ha);
hrb[lxy[x][i].e]=0;
}
return 0;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(k=1;k<=n;k++)
{
scanf("%d",&lxy[i][k].ha);
lxy[i][k].e=k;//记录列数
if(i!=1&&k==1)
maxn=min(maxn,lxy[i][1].ha),emm[i]=lxy[i][1].ha;
//求x到1的最小时间花费，用于预见性剪枝，和存x到1的花费用于搜索结算，解决排序造成的列乱序的情况
}
sort(lxy[i]+1,lxy[i]+n+1,cmp);
//STL大法好，二维数组的排序要用for，sort可以优化找出的答案minn，减少无用功
}
hrb[1]=1;//跑过了就要踩，不然会跑回去，想想80分代码为啥不用赋值为1？因为80分列没乱序
ss(1,1,0);
printf("%d",minn);
return 0;
}这题比较麻烦的是猜出题人意图，灵活运用贪心和预见性剪枝
其他的还是很水的
推荐两道题，运用预见性剪枝的p1731生日蛋糕和究极搜索
p1064金明的预算不要问为啥，有大佬写出来了