#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
#include <assert.h>
#define MAX 32
int CITYNUM=0;
const int INF=1000000000;
int map[MAX][MAX]={0};
int min[MAX][2];
struct EDGE
{
int cost[MAX][2];/*距离*/
int sta;
int lb,len;
char seq[MAX];
}q[1000000];
/*求下界*/
int calc(int cost[MAX][2],int n)
{
int sum=0,i;
for(i=0;i<n;i++)
{
if(cost[i][1]!=INF)
{
sum+=cost[i][0]+cost[i][1];
}
else if(cost[i][0]!=INF)
{
sum+=cost[i][0];
if(cost[i][0]==min[i][0])
sum+=min[i][1];
else sum+=min[i][0];
}
else
{
sum+=min[i][0]+min[i][1]; /*最小里面的一个，那么就是最小两个相加*/
}
}
if(sum&1)sum=sum/2+1;
else sum/=2;
return sum;
}
/*挑选*/
void BFS(int s,int n)
{
int front=-1,rear=0;
int i,step=0;
q[0].sta=1;
q[0].len=1;
q[0].seq[0]=””a””;
q[0].seq[1]=0;
for(i=0;i<n;i++)
q[0].cost[i][0]=q[0].cost[i][1]=INF;
while(front!=rear)
{
int size=rear-front;
step++;
int min=INF;
for(i=front+1;i<=rear;i++)
{
if(q[i].lb<min)
min=q[i].lb;
}
while(size–)
{
front++;
int sta=q[front].sta;
if(q[front].lb!=min)
continue;
for(i=0;i<n;i++)
{
int tsta;
char tseq[MAX]; /*存城市*/
int tlen=q[front].len+1;
strcpy(tseq,q[front].seq);
tseq[tlen-1]=i+””a””;
tseq[tlen]=0;
if(i==2&&(sta&2)==0)
{
printf(“%s”,tseq);
printf(“: error,C can””t before b\n”);
continue;
}
if((1<<i)&sta)
continue;
tsta=(1<<i)+sta;
rear++;
q[rear].sta=tsta;
strcpy(q[rear].seq,tseq);
q[rear].len=tlen;
memcpy(q[rear].cost,q[front].cost,sizeof(q[front].cost));
int from=q[front].seq[q[front].len-1]-“”a””;
if(q[rear].cost[i][0]==INF)
{
q[rear].cost[i][0]=map[from][i];
}
else
{
q[rear].cost[i][1]=map[from][i];
}
if(q[rear].cost[from][0]==INF)
{
q[rear].cost[from][0]=map[from][i];
}
else
{
q[rear].cost[from][1]=map[from][i];
}
q[rear].lb=calc(q[rear].cost,n);
printf(“%s”,tseq);
printf(“: lb=%d\n”,q[rear].lb);
}
}
}
}
/*自动生成文件*/
int main()
{
printf(“请输入城市的数目（大于1的整数）：”);
scanf(” %d”,&CITYNUM);
CITYNUM=CITYNUM-1;
int i = 0, ncount = CITYNUM, *val = 0;
int temp;
int loop;
int n=0,d,cnt=0;
char sa[10],sb[10];
int j;
FILE *fpp;
fpp = fopen(“in.dat”,”rb”);
while(fscanf(fpp,”%s%s%d”,sa,sb,&d)!=EOF) /*文件读取*/
{
sa[0]=sa[0]-“”a””;
sb[0]=sb[0]-“”a””;
if(sa[0]+1>n)
n=sa[0]+1;
if(sb[0]+1>n)
n=sb[0]+1;
map[sa[0]][sb[0]]=map[sb[0]][sa[0]]=d;
cnt++;
}
fclose(fpp);
for(i=0;i<n;i++)
map[i][i]=min[i][0]=min[i][1]=INF;
for(i=0;i<n;i++) /*把每个点最小的两个找出来*/
{
for(j=0;j<n;j++)
{
if(map[i][j]<=min[i][0])
{
min[i][1]=min[i][0];
min[i][0]=map[i][j];
}
else if(map[i][j]<min[i][1])
{
min[i][1]=map[i][j];
}
}
}
/*分支限界*/
BFS(0,n);
}
这是全部代码：
本人这部分看不懂：
void BFS(int s,int n)
{
int front=-1,rear=0;
int i,step=0;
q[0].sta=1;
q[0].len=1;
q[0].seq[0]=””a””;
q[0].seq[1]=0;
for(i=0;i<n;i++)
q[0].cost[i][0]=q[0].cost[i][1]=INF;
while(front!=rear)
{
int size=rear-front;
step++;
int min=INF;
for(i=front+1;i<=rear;i++)
{
if(q[i].lb<min)
min=q[i].lb;
}
while(size–)
{
front++;
int sta=q[front].sta;
if(q[front].lb!=min)
continue;
for(i=0;i<n;i++)
{
int tsta;
char tseq[MAX]; /*存城市*/
int tlen=q[front].len+1;
strcpy(tseq,q[front].seq);
tseq[tlen-1]=i+””a””;
tseq[tlen]=0;
if(i==2&&(sta&2)==0)
{
printf(“%s”,tseq);
printf(“: error,C can””t before b\n”);
continue;
}
if((1<<i)&sta)
continue;
tsta=(1<<i)+sta;
rear++;
q[rear].sta=tsta;
strcpy(q[rear].seq,tseq);
q[rear].len=tlen;
memcpy(q[rear].cost,q[front].cost,sizeof(q[front].cost));
int from=q[front].seq[q[front].len-1]-“”a””;
if(q[rear].cost[i][0]==INF)
{
q[rear].cost[i][0]=map[from][i];
}
else
{
q[rear].cost[i][1]=map[from][i];
}
if(q[rear].cost[from][0]==INF)
{
q[rear].cost[from][0]=map[from][i];
}
else
{
q[rear].cost[from][1]=map[from][i];
}
q[rear].lb=calc(q[rear].cost,n);
printf(“%s”,tseq);
printf(“: lb=%d\n”,q[rear].lb);
}
}
}
}
算法的思想本人知道，就是代码化了本人看不懂了。