Allocation Scheme

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB

Total submit users: 69, Accepted users: 64

Problem 10513 : No special judgement

Problem description

A manager of one company received a emergent project that needs to be completed in shortest time。With considering and analysing, the manager would divide the project into N independent tasks and that needs N employees to complete. Every ernployee can do any one of the N tasks, but the time is different. Please design a allocation scheme for the manager to make the task can be completed in shortest time.

Input

The number of the employees N begins with 0, so is the tasks number N. The time of every task done by every employee is stored in a two-dimensional array task_worker[N][N]. For example: task_worker[i][j] means the time of task i completed by employee j.

Output

The first row show the shortest time to complete the project.(unit: hour)

Output the situation of the allocation scheme.

Sample Input

10  11  12  11  9  1111  9   10  13  11  1212  10  11  10  13  99   14  9   10  10  1110  10  9   11  12  1110  7  10   10  10   8

Sample Output

The shortest time is 54 hoursTask 0 is distributed to employee 4Task 1 is distributed to employee 1Task 2 is distributed to employee 3Task 3 is distributed to employee 0Task 4 is distributed to employee 2Task 5 is distributed to employee 5

Problem Source

HNU Contest 

 

 

 

注意一下输入，要以文件结束。

code:

1  #include 
     
          2  #include 
      
           3  #include 
       
            4  #include 
        
             5  #include 
         
              6  #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                 
                   14 #include 
                  
                    15 #include 
                   
                     16 #include 
                    
                      17 #include 
                     
                       18 #include 
                      
                        19 using namespace std;20 21 int map[101][101];22 char str[101];23 int record[101];24 int record1[101];25 int vst[101];26 int mintime;27 int n;28 char t[101]; 29 30 void DFS(int cnt,int sum)31 {32 int i;33 if(cnt==n+1)34 {35 if(sum
                       
                        >t; 85 mintime=9999999;86 for(i=0;i<=n;i++)87 {88 memset(vst,0,sizeof(vst));89 memset(record,0,sizeof(record));90 vst[i]=1;91 record[0]=i;92 DFS(1,map[0][i]);93 }94 printf("The shortest time is %d hours\n",mintime);95 for(i=0;i<=n;i++)96 printf("Task %d is distributed to employee %d\n",i,record1[i]);97 }98 return 0;99 }