huisuo.cpp

算法设计课程设计中

#include <stdio.h>    
#include<stdlib.h>
#define NUM 35    
int d[NUM],c[NUM][NUM];    
int result = 0;    
void comp(int n);
void backtrack(int level,int n);     
  
int main() {    

    FILE* fpinput;    //指向输入文件input.txt
	FILE* fpoutput;    //指向输入文件output.txt
	//打开输入文件
	if((fpinput=fopen("input.txt","rt"))==NULL)
	{
		printf("\n打开文件input.txt出错!\n");
		system("PAUSE");
		exit(1);
	}
	//打开输出文件
	if((fpoutput=fopen("output.txt","wt"))==NULL)
	{
		printf("\n打开文件output.txt出错!\n");
		system("PAUSE");
		exit(1);
	}   
    int n;    
    fscanf(fpinput,"%n",&n) ;  
    for(int i = 1;i <= n;i++)    
        for(int j = 1;j <= n;j++)    
            scanf("%d",&c[i][j]);    
    for(i = 1;i <= n;i++)    
        d[i] = i;    
    backtrack(1,n);   
	fprintf(fpoutput,"%d\n",result); 

	fclose(fpinput);
	fclose(fpoutput);
	return 0;
}


void comp(int n) {    
	
    int sum = 0;    
    for(int i = 1; i <= n;i++)     
        sum += c[i][d[i]];    
    if(sum < result) {    
        result = sum;  
    }
}       
void backtrack(int level,int n) {    
	int temp;
    if(level > n)     
        comp(n);    
    else   
        for(int i = level;i <= n;i++) {
			temp=d[level];d[level]=d[i];d[i]=temp;   
            backtrack(level+1,n);
            temp=d[level];d[level]=d[i];d[i]=temp;
        }
}