#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define min(a,b) (a)<(b)?(a):(b)
#define V 5
int Length[V]={0};
int D[V][V]={
{0,6,4,5,8},
{6,0,3,2,7},
{4,3,0,3,1},
{5,2,3,0,2},
{8,7,1,2,0}
};
struct edge{
int fromV;
int toV;
int dist;
void set(int f,int t,int d){
fromV=f; toV=t; dist=d;
}
void operator=(const edge& e){
set(e.fromV,e.toV,e.dist);
}
};
static int comp(const void*e1,const void*e2){
if (((edge*)e1)->dist< ((edge*)e2)->dist)return -1;
else if(((edge*)e1)->dist==((edge*)e2)->dist)return 0;
else return 1;
}
const int len=16;
int Asum=0;
edge Path[V];
edge ArrE[len];
void printArrE(){
for(int p=0;p<len;++p){
printf("[%d,%d]=%d,",ArrE[p].fromV,ArrE[p].toV,ArrE[p].dist);
}
printf("\n");
}
void printPath(){
for(int p=0;p<V;++p){//printPath();
printf("[%d,%d]=%d,",Path[p].fromV,Path[p].toV,Path[p].dist);
}
printf("\n");
}
void checkResult(){
printPath();
for(int i=0;i<V;++i){
for(int j=i+1;j<V;++j){
if(Path[i].fromV==Path[j].toV && Path[i].toV==Path[j].fromV)return;
}
}
int sum[V]={0};
for(int s=0;s<V;++s){
sum[ Path[s].fromV ]++;
sum[ Path[s].toV ]++;
}
if(sum[0]==2 && sum[1]==2 && sum[2]==2 && sum[3]==2 && sum[4]==2){
printf("The best path is: ");
printPath();
exit(0);
}
}
#define x 1000
bool checkDuplicate(int c){
int F[V]={x,x,x,x,x};
int T[V]={x,x,x,x,x};
for(int i=0;i<V-c;++i){
int j=0;
do{
if(Path[i].fromV==F[j] || Path[i].toV==T[j]){
return true;
}
else{
F[j]=Path[i].fromV;
T[j]=Path[i].toV;
break;
}
++j;
}while(j<=i);
}
return false;
}
void replace(int c){//replace "count" elements at Path's tail
printPath();
if(checkDuplicate(c))return;
for(int k=V-c;k<V;++k)Path[k]=ArrE[k];//restore tail information
if(c==0){
checkResult();
return;
}
int start=V-c;
for(int i=start+1;i<len;++i){//i is the position in ArrE
Path[start]=ArrE[i];
replace(c-1);
}
}
int main(){
int tmp=V-1;
while(tmp){
Asum+=tmp;
--tmp;
}//For a solution, from/to vertex summary should be Asum
printf("Asum=%d\n",Asum);
int idx=0;
for(int r=0;r<V;++r){
for(int c=0;c<V;++c){
if(r==c)continue;
ArrE[idx++].set(r,c,D[r][c]);
}
}
qsort(ArrE,len,sizeof(edge),comp);
printArrE();
for(int i=0;i<V;++i){
memcpy(Path,ArrE,sizeof(edge)*V);
replace(i);
}
printf("No circle found\n");
return 0;
}
文章出处:飞诺网(www.diybl.com):http://www.diybl.com/course/3_program/c++/cppjs/20100628/212270.html