2631: 回溯法-旅行售货商问题

# include <stdio.h>
#define infinity 0x7fffffff // 表示无穷大 
#define MAX 20 //表示城市的最大个数 

int G[MAX+1][MAX+1]; //邻接矩阵，0号单元不存储信息 
int bestx[MAX+1]; //最优解，0号单元不存储信息
int x[MAX+1]; //当前解，0号单元不存储信息
int m,n; //n表示图中顶点(城市)个数，m表示图中边的个数 
int bestc;//最小成本 
int cc; //当前成本 

void createGraph(){
	
	int i,j,k,w;
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=n;i++){ //初始化邻接矩阵 
		for(j=1;j<=n;j++){
			G[i][j]=infinity;
		}
	}
	
	for(k=1;k<=m;k++){ //输入边的信息修改邻接矩阵
		scanf("%d %d %d",&i,&j,&w);
		G[i][j]=w;
		G[j][i]=w;
	}
		
}

void swap(int& x, int& y){
	int t=x;
	x=y;
	y=t;
}

void Traveling(int i){
	
	int j;
	
	if(i==n+1){
		if(G[x[n]][1]!=infinity && (cc+G[x[n]][1]<bestc)){ 
                  //如果x[n]与x[1]之间有边相连且当前费用加上该边的权小
		  //于当前找到的最优值，则找到了一个更好的解并做相应的更新操作 
			
		}
	}
	else{
		for(j=i;j<=n;j++){ 
                        //如果约束条件成立（x[i-1]和x[j]有边相连）和限界
			//条件成立（当前费用加上下一条边上的权小于当前最好值），
			//则交换下标为i的结点和下标为j的结点 
			if(G[x[i-1]][x[j]]!=infinity && (cc+G[x[i-1]][x[j]]<bestc)){
				
			}
		}
	}
}

void output(){
	int i;
	printf("%d\n",bestc);
	//旅行售货商问题是一个环路，从某个顶点出发最后还要回到该顶点
	for(i=1;i<=n;i++) printf("%d->",bestx[i]); 	
	printf("%d\n",bestx[1]); 
}

int main(void){
	createGraph();
	for(int i=1;i<=n;i++)  x[i]=i; //初始化解向量 
	bestc=infinity; //初始化最优成本为无穷大 
	cc=0; //初始化当前成本 
	Traveling(2); 
	// 从排列树中的第2层开始搜索，因为本题是一个特殊的排
	// 列树（x[1]的值为1且不发生变化） 
	output();
	return 0;
}

4 6
1 2 30
1 3 4
1 4 6
2 3 10
2 4 5
3 4 20

25
1->3->2->4->1