项目分配

Posted on by mannuan One min read
Table of Contents

项目分配

时间限制：C/C++语言 1000MS；其他语言 3000MS 内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

某公司雇有N名员工，每名员工可以负责多个项目，但一个项目只能交由一名员工负责。现在该公司接到M个项目，令A_{i,j}表示第i名员工负责第j个项目所带来的收益，那么如果项目分配得当，总收益最大是多少？

输入

第一行包含两个整数N和M，1≤N，M≤1000。

接下来N行，每行包含M个整数，第i行的第j个整数表示A{i,j}，1≤A{i,j}≤1000。

输出

输出总收益的最大值。

样例输入

3 3
1 3 3
2 2 2
3 2 1

样例输出

9

    # include<iostream>
    using namespace std;

    int n,m,cost =0;
    int x[1001],c[1001][1001];

    void work(int i, int count){
        if(i>n&&count>cost){
            cost=count;
            return ;
        }
        if(count>cost){
            for(int j=1;j<=m;j++){
                if(x[j]==0){
                    x[j] = 1;
                    work(i+1, count+c[i][j]);
                    x[j] =0;
                }
            }
        }
    }

    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>c[i][j];
                c[i][j] = -c[i][j];
                x[j] = 0;
            }
            cost+=c[i][i];
        }
        work(1, 0);
        cout<<-cost<<endl;
        return 0;
    }