任务分配问题

た入场券 2022-05-27 07:42 177阅读 0赞

只有一组测试用例。 输入：第一行是操作员的人数n(4=<n<=13)，接下来的n行里每行有n个数，分别表示第i名操作员完成第i项任务的时间。 输出：完成所有任务的最短时间。

<table style="max-width:100%;border-spacing:0px;width:1669px;margin-bottom:20px;background-color:transparent;"> 
 <thead> 
  <tr> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">&nbsp;</th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">测试输入<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">期待的输出<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">时间限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">内存限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">额外进程<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">测试用例 1</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);"><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=71146&amp;test=90963&amp;type=in&amp;download=0" style="color:rgb(67,142,185);font-size:9pt;" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top;padding:0px 5px 0px 0px;width:10em;height:10em;"> 
     <ol style="margin-bottom:0px;margin-left:2.5em;"> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">4↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">3&nbsp;8&nbsp;4&nbsp;12↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">9&nbsp;12&nbsp;13&nbsp;5↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">8&nbsp;7&nbsp;9&nbsp;3↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">12&nbsp;7&nbsp;6&nbsp;8↵</span></li> 
     </ol> 
    </div></td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);"><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=71146&amp;test=90963&amp;type=out&amp;download=0" style="color:rgb(67,142,185);font-size:9pt;" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top;padding:0px 5px 0px 0px;width:10em;height:10em;"> 
     <ol style="margin-bottom:0px;margin-left:2.5em;"> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">21↵</span></li> 
     </ol> 
    </div></td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">1秒</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">64M</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">0</td> 
  </tr> 
 </tbody> 
</table>

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define Min 0x7fffffff
    int n;
    int workers[14][14];
    bool flag[14];//任务标记
    int mins;
    int miN[14];//每列用时最小
    
    void dfs(int k,int time)//k代表到第几个员工，time是当前总用时-
    {
    	int minsum; int j;
    	if (k >= n+1){//到达搜索终点从新得到答案
    		mins = min(mins, time);
    		return; }
    	if (time > mins) return;//剪枝1，如果当前所用时间time
    	for (int i = 1; i<=n; i++)//枚举任务
    	{
    		if (!flag[i])
    		{
    			//剪枝2，,若没选中的任务列最小值之和比mins大,那就直接剪掉了  
    			for (minsum = time + workers[k][i], j = 1; j <= n; j++)
    			{
    				if (!flag[j] && j != i)
    					minsum += miN[j];
    			}
    			if (minsum < mins)
    			{
    				flag[i] = true;//表示这个任务做过了
    				dfs(k + 1, time + workers[k][i]);
    				flag[i] = false;//去掉这个任务做过的标记
    			}
    		}
    	}
    }
    
    int main()
    {
    	//freopen("1.txt","r",stdin);
    
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{ 
    		miN[i] = Min;
    	    for (int j = 1; j <= n; j++)
    		cin >> workers[i][j];
    	}
    
    
    
    	for (int i = 1; i <= n; i++)
    	for (int j = 1; j <= n; j++)
    	if (workers[i][j] < miN[j])
    		miN[j] = workers[i][j]; //找到每一列的最小值  
    
    	mins = Min;
    	dfs(1,0);
    	cout << mins<<endl;
    	return 0;
    }