程序填空题：求解任务分配问题（回溯法）

有n（n≥1）个任务需要分配给n个人执行，每个任务只能分配给一个人，每个人只能执行一个任务。第i个人执行第j个任务的成本是c[i][j]（1≤i，j≤n）。求出总成本最小的分配方案。

```c++
#include
#include
#include
using namespace std;
#define INF 99999 //定义∞
#define MAXN 20
int n;
int c[MAXN][MAXN]={0}; //下标0的元素不用
int x[MAXN]; //临时解
int cost=0; //临时解的成本
int bestx[MAXN]; //最优解
int mincost=INF; //最优解的成本
bool worker[MAXN]; //worker[j]表示任务j是否已经分配人员

void dfs(int i) //为第i个人员分配任务
{
if (i>n) //到达叶子结点
{
if (cost {
;
for (int j=1;j<=n;j++)
;
}
}
else
{
for (int j=1;j<=n;j++) //为人员i试探任务j:1到n
if () //若任务j还没有分配
{
worker[j]=true;
; //任务j分配给人员i
cost+=c[i][j];
; //为人员i+1分配任务
worker[j]=false; //回退
x[j]=0;
;
}
}
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&c[i][j]);
memset(worker,0,sizeof(worker)); //worker初始化为false
dfs(1); //从人员1开始
for (int k=1;k<=n;k++)
printf("%d %d\n",k,bestx[k]);
printf("%d",mincost);
return 0;
}

```

### 输入格式:

第1行输入人数n。接下来输入n行，每行n个数，表示第i个人执行第j个任务的成本（w人员及任务编号从1到n）。

### 输出格式:

先输入分配方案：按人员编号递增顺序依次输出n行，每行两个数，分别表示人员编号和任务编号。最后再输出总成本

### 输入样例:

```in
4
9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 4
```

### 输出样例:

```out
1 2
2 1
3 3
4 4
13
```





答案：
第1空：mincost=cost

第2空：bestx[j]=x[j]

第3空：!worker[j]

第4空：x[i]=j

第5空：dfs(i+1)

第6空：cost-=c[i][j]