1084:XX开公司<回溯>
2024-09-13 21:33:10
Description
2020年，xx开了一家拥有N个员工的大公司。每天，xx都要分配N项工作给他的员工，但是，由于能力的不同，每个人对处理相同工作所需要的时间有快有慢。众所周知，xx是一个非常重视效率的人，他想知道该如何分配工作，才能使得完成所有工作的时间总和最小（每个员工只可以被分配到一个工作）。但是我们也都知道xx不是一般的懒，所以xx找到了你，请你拯救一下xx吧！
Input
有多组测试数据。（不超过50组）
对于每组测试数据：
第一行输入一个整数N，代表有N员工，员工编号从1到N。（1 <= N <= 10，N >= 8的数据只有3组）
接着输入一个N*N的二维矩阵task[N][N]，task[i][j]指的是第i项工作如果由j号员工完成所需要的时间。（0 <= task[i][j] <= 1000）
Output
输出结果包括一个整数，代表所需要的最少时间（求和）。
6
10 11 12 11 9 11
11 9 10 13 11 12
12 10 11 10 13 9
9 14 9 10 10 11
10 10 9 11 12 11
10 7 10 10 10 8
54
#include<iostream>#include<cstdio>
using namespace std;
int n,cost=0;
int x[100],c[100][100];
void work(int i,int count){
if(i>n&&count<cost){
cost=count;
return ;
}
if(count<cost)
for(int j=1;j<=n;j++)
if(x[j]==0){
x[j]=1;
work(i+1,count+c[i][j]);
x[j]=0;
}
}
int main ()
{
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
scanf("%d",&c[i][j]);
x[i]=0;
cost+=c[i][i];
}
work(1,0);
printf("%d\n",cost);
}
return 0;
}
最新文章
- Windbg Extension NetExt 使用指南 【3】 ---- 挖掘你想要的数据 Managed Heap
- mrjob 使用 mongodb 作为数据源
- isMobile
- centos7 安装lamp
- ubuntu 12.10 sourcelist软件更新源列表(zz)
- Android资料之-EditText中的inputType
- Mac & XCode 使用技巧总结
- [Javascript] Limit Built Branches on Travis
- Objective-C中常用的结构体NSRange,NSPoint,NSSize(CGSize),NSRect
- Windows CPU占用率过高
- “0x5003eaed” 指令引用的“0x00000000”内存。该内存不能为“read”
- C语言学习_include<>与include""的区别
- C指针--通过二级指针往回拉数据
- Ant学习实例
- docker安装升级linux内核(2.6.32->3.12.17)
- HTML中的a标签实现点击下载
- 使用VLC和live555MediaServer搭建RTSP服务器
- 20165235 学习基础和C语言基础调查
- [JAVA]JAVA章3 如何获取及查看DUMP文件
- 百度前端学院task33源码及总结——听指令的小方块