给定n个任务和m个人,每个任务需要由某个人来完成,完成任务需要一定的时间。每个人一次只能完成一个任务,每个任务一次只能由一个人完成。请确定完成所有任务的最短时间。求C语言
时间: 2024-02-13 12:01:45 浏览: 205
在一个给定范围的区间内找到该区间所有的质数(素数)
以下是使用匈牙利算法求解任务分配问题的C语言代码示例:
```c
#include <stdio.h>
#include <string.h>
#define MAX_N 100
#define MAX_M 100
int n, m;
int task_time[MAX_N][MAX_M]; // 完成任务所需的时间
int match[MAX_M]; // 匹配情况
int vis[MAX_M]; // 是否访问过
// 尝试为任务i匹配一个可行的人员
int dfs(int i) {
for (int j = 0; j < m; j++) {
if (task_time[i][j] && !vis[j]) { // 如果任务i与人员j之间有边且人员j未被访问过
vis[j] = 1; // 标记人员j已被访问过
if (match[j] == -1 || dfs(match[j])) { // 如果人员j未匹配或人员match[j]可以换任务
match[j] = i; // 匹配任务i和人员j
return 1;
}
}
}
return 0;
}
// 计算完成所有任务的最短时间
int min_time() {
int res = 0;
memset(match, -1, sizeof(match)); // 初始化匹配情况
for (int i = 0; i < n; i++) {
memset(vis, 0, sizeof(vis)); // 初始化访问情况
if (dfs(i)) {
res += 1; // 匹配成功,任务数量加1
}
}
int time = 0;
for (int j = 0; j < m; j++) {
if (match[j] != -1) {
time += task_time[match[j]][j]; // 计算匹配的任务所需的总时间
}
}
return time;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &task_time[i][j]);
}
}
int res = min_time();
printf("%d\n", res);
return 0;
}
```
此代码使用DFS来寻找增广路径,时间复杂度为$O(nm^2)$。
阅读全文