17085 工作分配问题

 

17085 工作分配问题（必做）

时间限制:20000MS  内存限制:65535K
提交次数:0 通过次数:0

题型: 编程题   语言: C++;C;VC;JAVA

Description

有n件工作分配给n个人，将工作i分配给第j个人需要支付劳务费用Cij。请为每人分配一个工作，并使得总劳务费用达到最小。

 

 

 

输入格式

第一行一个正整数n（1<=n<=11），表示n个工作数，接下来n行，每行代表第i个工作支付给n个不同的人的劳务费用。

 

 

输出格式

两行。
第一行为最小的总劳务费用。
第二行有n个数，表示工作分配方案。
如下面sample用例的测试数据：
第二行是2 1 3，表示第1个工作分配给第2个人，第2个工作分配给第1个人，第3个工作分配给第3个人。 2+2+5=9
当同时有多种分配方案都能使得总劳务费用相同且都最小，小编号工作优先分配给小编号的人，仅输出这一种方案即可。

 

 

输入样例

3
10 2 3
2 3 4
3 4 5

 

 

输出样例

9
2 1 3

 

#include <iostream>

#include <stdio.h>

using namespace std;

int n;

int cost=0; //当前费用

int resC=100000;  //最小费用

int c[100][100];  //费用表

int m[100]={0};  // 分配表

int res[100];  //最终分配表

void dfs(int deep){

    if(deep>n-1){

            //cout <<cost;

        if(cost<resC) {  

//小编号工作优先分配给小编号的人 注意边界

                resC = cost;

                for(int i=0;i<n;i++) // 跟新最小分配

                    res[i]=m[i];

        }

    }else{

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

                if(m[i]==0){

 

          cost+=c[i][deep]; 

 //每行代表第i个工作支付给n个不同的人的劳务费用!!!!!!

          m[i] = deep+1;  // 记录分配的任务编号

          if(cost<resC)   //剪枝

          dfs(deep+1);

          cost-=c[i][deep];

          m[i] = 0;

                }

 

        }

 

    }

}

int main()

{

    freopen("in.txt","r",stdin);

    cin >>n;

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

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

        cin >> c[i][j];

    dfs(0);

    cout << resC << endl;

    //2 1 3，表示第1个工作分配给第2个人，第2个工作分配给第1个人，第3个工作分配给第3个人。

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

        cout << res[i] <<" ";

    return 0;

}