7-11 工作分配问题 （20 分）

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。

输入格式:

输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。

输出格式:

将计算出的最小总费用输出到屏幕。

输入样例:

在这里给出一组输入。例如：

3

10 2 3

2 3 4

3 4 5

输出样例:

在这里给出相应的输出。例如：

9

作者: 陈晓梅

单位: 广东外语外贸大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

还以为是DP 看了题解 没想到这么暴力都行 只跑了4ms N  <= 20 本来想写回溯的不自觉写成位运算了 唯一的剪枝就是ans的大小和新生成的cost进行比较

#include <stdio.h>

int map[22][22];

int ans = 200000000;

int n;

void dfs(int layer, int cost, int di) {//layer用于指示工作 第layer个工作 distribution

if (layer == n) {

if (ans > cost) ans = cost;

return;

}

if (ans <= cost) return;

for (int i = 0; i < n; i++) {

if (di >> i & 1) continue;

int nd = di | 1 << i;

int nc = cost + map[layer][i];

if (ans <= nc) continue;

dfs(layer + 1, nc, nd);

}

}

int main() {

scanf("%d", &n);

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

scanf("%d", &map[i][j]);

dfs(0, 0, 0);

printf("%d\n", ans);

return 0;

}