工作分配问题

你的名字 2022-02-15 04:59 150阅读 0赞

### 工作分配问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

Problem Description

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

Input

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

Output

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

Sample Input

3
    10 2 3
    2 3 4
    3 4 5

Sample Output

9

#include <bits/stdc++.h>
    
    using namespace std;
    
    int n, c[22][22], vis[22], mininum;
    
    void dfs(int i, int sum)
    {
        if(sum > mininum)
            return;
        if(i == n + 1 && sum < mininum)
        {
            mininum = sum;
            return;
        }
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j])
            {
                vis[j] = 1;
                dfs(i + 1, sum + c[i][j]);
                vis[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]);
            }
        }
        mininum = INT_MAX;
        dfs(1, 0);
        printf("%d\n", mininum);
        return 0;
    }

[Submit]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2851/pid/1776.html
[Statistic]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2851/pid/1776.html

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关动态内存分配是如何工作的

动态内存分配是指在程序运行期间根据需要可以动态地分配和释放内存的过程。在动态内存分配中，内存可以根据需要随时分配和释放，这使得程序开发者可以更有效地利用内存，更好地支持程序运行

た入场券/ 2024年03月25日 16:07/ 0 赞/ 30 阅读

相关工作分配问题——算法设计与分析（C实现）

目录一、问题描述二、问题分析三、代码展示四、结果验证 -------------------- 一、问题描述问题描述：设有n件工作分配给n个人。将

秒速五厘米/ 2024年03月17日 11:11/ 0 赞/ 36 阅读

相关子集和问题工作分配问题回溯法实验

实验名称：回溯法一、实验预习 1、实验目的 1. 理解并掌握回溯法的设计思想； 2. 提高应用回溯法解决问题和设计算法的能力； 3. 通过编程实现子集和问题和工

港控/mmm°/ 2023年09月28日 08:27/ 0 赞/ 111 阅读

相关 PTA--工作分配问题

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

你的名字/ 2022年12月27日 12:36/ 0 赞/ 140 阅读

相关任务分配问题

<table style="max-width:100%;border-spacing:0px;width:1669px;margin-bottom:20px;backgrou

た入场券/ 2022年05月27日 07:42/ 0 赞/ 173 阅读

相关工作分配问题

工作分配问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n件工作分配给n个人

男娘i/ 2022年04月24日 11:00/ 0 赞/ 136 阅读

相关任务分配问题

问题描述：假设有n个任务需要分配给n个人执行，每个人只执行一个任务，每个任务只由一个人执行。第i个人执行第j个任务的成本是Cij(1<=i,j<=n), 求解初最小成本

柔光的暖阳◎/ 2022年04月16日 05:07/ 0 赞/ 208 阅读

相关 1776 工作分配问题

工作分配问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n件工作分配给n个人

淩亂°似流年/ 2022年02月15日 06:24/ 0 赞/ 127 阅读

相关工作分配问题

工作分配问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem

你的名字/ 2022年02月15日 04:59/ 0 赞/ 151 阅读

相关委派模式——分配工作任务

一代码位置 [https://gitee.com/cakin24/javatest][https_gitee.com_cakin24_javatest] 二代码 1

骑猪看日落/ 2021年07月24日 16:34/ 0 赞/ 303 阅读