test_time.cpp

匈牙利算法求解最优分配问题

#include <stdio.h>
#include <stdlib.h>
#include <sys/timeb.h>
#include <time.h>
#include <math.h>
#include <assert.h>
#include <string.h>

#include "hungarian.h"

#define MAXUTIL 100

#ifndef max
  #define max(a, b) ((a) > (b) ? (a) : (b))
#endif

#define USAGE "Usage: ./test [-m <m>] [-n <n>]"

// problem dimensions
int m,n;

void parse_args(int argc, char** argv);
int* make_random_r(int m, int n);

int main(int argc, char** argv)
{
	hungarian_t prob;	
	m = n = 4;	
	parse_args(argc,argv);
	int* r;	
	r = make_random_r(m,n);//行数必须小于或等于列数
	/*	int r[4][4] =  {{  -100, -80, -20,  -10  },
	{  -10, -100, -20, -100  },
	{  -15,  -80, -80, -70  },
	{  -15,  -33, -80, -70  }};

	int r[4][4] =  {{  363, 626, 376,  46  },
	{  802, 993, 784, 953  },
	{  673,  23, 823, 207  },
	{  380, 451, 520, 646  }};

	*/	
	//计算起始时间
	struct _timeb timebuffer1,timebuffer2;
	_ftime( &timebuffer1);
	int t1=timebuffer1.time;
	
	hungarian_init(&prob,(int*)r,m,n,HUNGARIAN_MIN);
	hungarian_print_rating(&prob);
	hungarian_solve(&prob);
	hungarian_print_assignment(&prob);
	
	//计算结束时间
    _ftime( &timebuffer2);
    int t2=timebuffer2.time;
    double usedTime=(t2-t1)+(timebuffer2.millitm-timebuffer1.millitm)*1e-6; 
    printf("The used time is %f\n",usedTime);
	
	
	printf("\nfeasible? %s\n", 
		(hungarian_check_feasibility(&prob)) ? "yes" : "no");
	printf("benefit: %d\n\n", hungarian_benefit(&prob));
	
	hungarian_fini(&prob);
	free(r);
	return(0);
}

/*
 * makes and returns a pointer to an mXn rating matrix with values uniformly 
 * distributed between 1 and MAXUTIL
 *
 * allocates storage, which the caller should free().
 */
int* make_random_r(int m, int n)
{
  int i,j;
  int* r;
  time_t curr;
  assert(r = (int *)malloc(sizeof(int)*m*n));
  curr = time(NULL);
  srand(curr);
  //puts("\nINPUT: ");
  for(i=0;i<m;i++)
  {
    //printf("  [ ");
    for(j=0;j<n;j++)
    {
      r[i*n+j] = 1+(rand() % MAXUTIL);
      //printf("%4d ", r[i*n+j]);
    }
    //puts(" ]");
  }
  return(r);
}

void parse_args(int argc, char** argv)
{
  int i;
  // parse command-line args
  for(i=1; i<argc; i++)
  {
    if(!strcmp(argv[i],"-m"))
    {
      if(++i < argc)
      {
        m = atoi(argv[i]);
      }
      else
      {
        puts(USAGE);
        exit(-1);
      }
    }
    else if(!strcmp(argv[i],"-n"))
    {
      if(++i < argc)
      {
        n = atoi(argv[i]);
      }
      else
      {
        puts(USAGE);
        exit(-1);
      }
    }
    else
    {
      puts(USAGE);
      exit(-1);
    }
  }
}