## 方法一：回溯法

n分作业分配给n个人，共有n!中排列方式，深度优先遍历其排列数，如果遍历的路径已经比当前最小的话费则舍弃对当前路径的遍历，返回上层节点，寻找合适的路径，即回溯，如果最后可行解比当前的最小费用小，那么就更新最佳的作业安排顺序，同时更新最小的耗费时间。

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 `````` ``````#include #include #include #include #include int N; /*表示任务数和工人数*/ //c[i][j] 工人i完成工作j所需的费用 //task[i] 值为0表示任务i未分配，值为1表示任务已分配 //work[k] 值为0表示工人k未分配任务，值为j表示工人k已分配任务j //mincost 最小总费用 int **c; int mincost = INT32_MAX; int *task, *temp, *worker; void Plan(int k, int cost) { int i, j; if (k >= N && cost < mincost) { mincost = cost; for (i = 0; i < N; i++) temp[i] = task[i]; //记录工作分配，如只要输出最小费用，无需输出分配情况，可删除此循环及work, temp数组 } else { for (j = 0; j < N; j++) if (task[j] == 0 && cost + c[k][j] < mincost) { worker[k] = j; task[j] = 1; //分配 Plan(k + 1, cost + c[k][j]); worker[k] = 0; task[j] = 0; //回溯 } } } int main(int argc, char const *argv[]) { int i, j; scanf("%d", &N); c = (int **)malloc(sizeof(int *) * N); for (i = 0; i < N; i++) c[i] = (int *)malloc(sizeof(int) * N); task = (int *)malloc(sizeof(int) * N); worker = (int *)malloc(sizeof(int) * N); temp = (int *)malloc(sizeof(int) * N); for (i = 0; i < N; i++) { worker[i] = 0; task[i] = 0; temp[i] = 0; for (j = 0; j < N; j++) scanf("%d", &c[i][j]); //mincost += c[i][i]; } Plan(0, 0); free(task); free(worker); free(temp); for (i = 0; i < N; i++) free(c[i]); free(c); printf("\n Mincost = %d\n", mincost); for (i = 0; i < N; i++) printf("Worker %d is assigned task %d\n", i, temp[i]); return 0; } ``````

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 `````` ``````#include #include #include int **aray; int *list; int number; int final_cost = 0; int current_cost = 0; void swap(int *a,int *b) { int temp; temp = *a; *a = *b; *b = temp; } void search(int k) { int i; if(k >= number) { final_cost=current_cost; } else { for(i = k; i < number; i++) { current_cost += aray[k][list[i]]; if(current_cost < final_cost) { swap(&list[k], &list[i]); search(k+1); swap(&list[k], &list[i]); } current_cost -= aray[k][list[i]]; } } } int main() { int m; int i,j; scanf("%d", &number); aray = (int **)malloc(sizeof(int *)*number); list = (int *)malloc(sizeof(int)*number); for(i = 0; i < number; i++) list[i] = i; for(i = 0;i < number; i++) aray[i] = (int *)malloc(sizeof(int)*number); for(i = 0; i < number; i++) { for(j = 0; j < number; j++) { scanf("%d", &aray[i][j]); } final_cost += aray[i][i]; } search(0); printf("%d\n", final_cost); free(list); free(aray); return 0; } ``````

## 方法二：匈牙利算法

http://zh.wikipedia.org/wiki/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 `````` ``````#define N 55 //max number of vertices in one part #define INF 100000000 //just infinity int cost[N][N]; //cost matrix int n, max_match; //n workers and n jobs int lx[N], ly[N]; //labels of X and Y parts int xy[N]; //xy[x] - vertex that is matched with x, int yx[N]; //yx[y] - vertex that is matched with y bool S[N], T[N]; //sets S and T in algorithm int slack[N]; //as in the algorithm description int slackx[N]; //slackx[y] such a vertex, that // l(slackx[y]) + l(y) - w(slackx[y],y) = slack[y] int prev[N]; //array for memorizing alternating paths void init_labels() { memset(lx, 0, sizeof(lx)); memset(ly, 0, sizeof(ly)); for (int x = 0; x < n; x++) for (int y = 0; y < n; y++) lx[x] = max(lx[x], cost[x][y]); } void augment() //main function of the algorithm { if (max_match == n) return; //check wether matching is already perfect int x, y, root; //just counters and root vertex int q[N], wr = 0, rd = 0; //q - queue for bfs, wr,rd - write and read //pos in queue memset(S, false, sizeof(S)); //init set S memset(T, false, sizeof(T)); //init set T memset(prev, -1, sizeof(prev)); //init set prev - for the alternating tree for (x = 0; x < n; x++) //finding root of the tree if (xy[x] == -1) { q[wr++] = root = x; prev[x] = -2; S[x] = true; break; } for (y = 0; y < n; y++) //initializing slack array { slack[y] = lx[root] + ly[y] - cost[root][y]; slackx[y] = root; } //second part of augment() function while (true) //main cycle { while (rd < wr) //building tree with bfs cycle { x = q[rd++]; //current vertex from X part for (y = 0; y < n; y++) //iterate through all edges in equality graph if (cost[x][y] == lx[x] + ly[y] && !T[y]) { if (yx[y] == -1) break; //an exposed vertex in Y found, so //augmenting path exists! T[y] = true; //else just add y to T, q[wr++] = yx[y]; //add vertex yx[y], which is matched //with y, to the queue add_to_tree(yx[y], x); //add edges (x,y) and (y,yx[y]) to the tree } if (y < n) break; //augmenting path found! } if (y < n) break; //augmenting path found! update_labels(); //augmenting path not found, so improve labeling wr = rd = 0; for (y = 0; y < n; y++) //in this cycle we add edges that were added to the equality graph as a //result of improving the labeling, we add edge (slackx[y], y) to the tree if //and only if !T[y] && slack[y] == 0, also with this edge we add another one //(y, yx[y]) or augment the matching, if y was exposed if (!T[y] && slack[y] == 0) { if (yx[y] == -1) //exposed vertex in Y found - augmenting path exists! { x = slackx[y]; break; } else { T[y] = true; //else just add y to T, if (!S[yx[y]]) { q[wr++] = yx[y]; //add vertex yx[y], which is matched with //y, to the queue add_to_tree(yx[y], slackx[y]); //and add edges (x,y) and (y, //yx[y]) to the tree } } } if (y < n) break; //augmenting path found! } if (y < n) //we found augmenting path! { max_match++; //increment matching //in this cycle we inverse edges along augmenting path for (int cx = x, cy = y, ty; cx != -2; cx = prev[cx], cy = ty) { ty = xy[cx]; yx[cy] = cx; xy[cx] = cy; } augment(); //recall function, go to step 1 of the algorithm } }//end of augment() function void update_labels() { int x, y, delta = INF; //init delta as infinity for (y = 0; y < n; y++) //calculate delta using slack if (!T[y]) delta = min(delta, slack[y]); for (x = 0; x < n; x++) //update X labels if (S[x]) lx[x] -= delta; for (y = 0; y < n; y++) //update Y labels if (T[y]) ly[y] += delta; for (y = 0; y < n; y++) //update slack array if (!T[y]) slack[y] -= delta; } void add_to_tree(int x, int prevx) //x - current vertex,prevx - vertex from X before x in the alternating path, //so we add edges (prevx, xy[x]), (xy[x], x) { S[x] = true; //add x to S prev[x] = prevx; //we need this when augmenting for (int y = 0; y < n; y++) //update slacks, because we add new vertex to S if (lx[x] + ly[y] - cost[x][y] < slack[y]) { slack[y] = lx[x] + ly[y] - cost[x][y]; slackx[y] = x; } } int hungarian() { int ret = 0; //weight of the optimal matching max_match = 0; //number of vertices in current matching memset(xy, -1, sizeof(xy)); memset(yx, -1, sizeof(yx)); init_labels(); //step 0 augment(); //steps 1-3 for (int x = 0; x < n; x++) //forming answer there ret += cost[x][xy[x]]; return ret; } ``````