程序填空题：求解任务分配问题(分枝限界法)

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

```c++
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f //定义∞
#define MAXN 21
int n;
int c[MAXN][MAXN]; //下标0的元素不用
int bestx[MAXN]; //最优分配方案
int mincost=INF; //最小成本
int total=1; //结点个数累计
struct NodeType //队列结点类型
{
int no; //结点编号
int i; //人员编号
int x[MAXN]; //x[i]为人员i分配的任务编号
bool worker[MAXN]; //worker[i]=true表示任务i已经分配
int cost; //已经分配任务所需要的成本
int lb; //下界
bool operator<(const NodeType &s) const //重载<关系函数
{
return lb>s.lb;
}
};

void bound(NodeType &e) //求结点e的限界值
{
int minsum=0;
for (int i1=e.i+1;i1<=n;i1++) //求c[e.i+1..n]行中最小元素和
{
int minc=INF;
for (int j1=1;j1<=n;j1++)
if (@@[e.worker[j1]==false && c[i1][j1] minc=c[i1][j1];
minsum+=minc;
}
e.lb=@@[e.cost+minsum](2);
}

void bfs() //求解任务分配
{
int j;
NodeType e,e1;
priority_queue qu;
memset(e.x,0,sizeof(e.x)); //初始化根结点的x
memset(e.worker,0,sizeof(e.worker)); //初始化根结点的worker
e.i=0; //根结点，指定人员为0
e.cost=0;
bound(e); //求根结点的lb
e.no=total++;
qu.push(e); //根结点进队列
while (!qu.empty())
{
e=qu.top(); qu.pop(); //出队结点e，当前考虑人员e.i
if (@@[e.i==n](2))
{
if (@@[e.cost {
mincost=e.cost;
for (j=1;j<=n;j++)
bestx[j]=e.x[j];
}
}
e1.i=e.i+1; //扩展分配下一个人员的任务，对应结点e1
for (j=1;j<=n;j++) //考虑n个任务
{
if (e.worker[j]) continue; //任务j是否已分配人员,若已分配，跳过
for (int i1=1;i1<=n;i1++) //复制e.x得到e1.x
e1.x[i1]=@@[e.x[i1]](1);
e1.x[e1.i]=@@[j](1);
for (int i2=1;i2<=n;i2++)
e1.worker[i2]=@@[e.worker[i2]](1);
e1.worker[j]=@@[true](1);
e1.cost=@@[e.cost+c[e1.i][j]](2);
bound(e1); //求e1的lb
e1.no=total++;
if (@@[e1.lb<=mincost](2)) //剪枝
qu.push(e1);
}
}
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&c[i][j]);
bfs();
for (int k=1;k<=n;k++)
printf("%d %d\n",k,bestx[k]);
printf("%d",mincost);
return 0;
}


```





答案：
第1空：e.worker[j1]==false && c[i1][j1]
第2空：e.cost+minsum

第3空：e.i==n

第4空：e.cost
第5空：e.x[i1]

第6空：j

第7空：e.worker[i2]

第8空：true

第9空：e.cost+c[e1.i][j]

第10空：e1.lb<=mincost