int inq[22]; //确定上界
int dfs(int u,int k,int l) {
if(k==n) return l+mp[u][1]; int minlen=INF , p; for(int i=1; i<=n; i++) {
if(inq[i]==0&&minlen>mp[u][i])/*取与所有点的连边中最小的边*/ {
minlen=mp[u][i]; p=i; } } inq[p]=1;
return dfs(p,k+1,l+minlen); }
int get_lb(node p) {
int ret=p.sumv*2;//路径上的点的距离
int min1=INF,min2=INF;//起点和终点连出来的边 for(int i=1; i<=n; i++) {
if(p.visp[i]==0&&min1>mp[i][p.st]) {
min1=mp[i][p.st]; } }
ret+=min1;
for(int i=1; i<=n; i++)
11
{
if(p.visp[i]==0&&min2>mp[p.ed][i]) {
min2=mp[p.ed][i]; } }
ret+=min2;
for(int i=1; i<=n; i++) {
if(p.visp[i]==0) {
min1=min2=INF;
for(int j=1; j<=n; j++) {
if(min1>mp[i][j]) min1=mp[i][j]; }
for(int j=1; j<=n; j++) {
if(min2>mp[j][i]) min2=mp[j][i]; }
ret+=min1+min2; } }
return ret%2==0?(ret/2):(ret/2+1); }
void get_up() {
inq[1]=1;
12
up=dfs(1,1,0); }
void get_low() {
low=0;
for(int i=1; i<=n; i++) {
/*通过排序求两个最小值*/ int min1=INF,min2=INF; int tmpA[22];
for(int j=1; j<=n; j++) {
tmpA[j]=mp[i][j]; }
sort(tmpA+1,tmpA+1+n);//对临时的数组进行排序 low+=tmpA[1]; } }
int solve() {
/*贪心法确定上界*/ get_up();
/*取每行最小的边之和作为下界*/ get_low();
/*设置初始点,默认从1开始 */ node star; star.st=1; star.ed=1;
13
star.k=1;
for(int i=1; i<=n; i++) star.visp[i]=0; star.visp[1]=1; star.sumv=0; star.lb=low;
/*ret为问题的解*/ int ret=INF;
q.push(star); while(!q.empty()) {
node tmp=q.top(); q.pop(); if(tmp.k==n-1) {
/*找最后一个没有走的点*/ int p;
for(int i=1; i<=n; i++) {
if(tmp.visp[i]==0) { p=i; break; } }
int ans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p]; node judge = q.top();
/*如果当前的路径和比所有的目标函数值都小则跳出*/
14
if(ans <= judge.lb) {
ret=min(ans,ret); break; }
/*否则继续求其他可能的路径和，并更新上界*/ else {
up = min(up,ans); ret=min(ret,ans); continue; } }
/*当前点可以向下扩展的点入优先级队列*/ node next;
for(int i=1; i<=n; i++) {
if(tmp.visp[i]==0) {
next.st=tmp.st;
/*更新路径和*/
next.sumv=tmp.sumv+mp[tmp.ed][i];
/*更新最后一个点*/ next.ed=i;
/*更新顶点数*/ next.k=tmp.k+1;
15