Chinaunix首页 | 论坛 | 博客
  • 博客访问: 486677
  • 博文数量: 25
  • 博客积分: 111
  • 博客等级: 民兵
  • 技术积分: 1279
  • 用 户 组: 普通用户
  • 注册时间: 2012-10-26 20:51
文章分类

全部博文(25)

文章存档

2014年(17)

2013年(8)

分类: C/C++

2014-04-13 14:25:24

本文主要是对2014微软编程之美的一道题(格格取数)的解答,用的是贪心算法。问题如下:

给你一个m x n (1 <= m, n <= 100)的矩阵A (0<=aij<=10000),要求在矩阵中选择一些数,要求每一行,每一列都至少选到了一个数,使得选出的数的和尽量的小。

本算法主要分两步,作简要说明:1、为了是每行每列都去到,我们分别对每行每列取最小值;2、在取得这些数值中可能存在多余的数值,对于这些数值我们进行两种处理:(1)看看可不可以直接删除,(2)看看可不可以进行转换

点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <vector>
  3. #include <map>

  4. using namespace std;

  5. int row,col;
  6. vector<int> m_row,m_col;
  7. vector<vector<int> >matrix;
  8. vector<vector<bool> >mark;
  9. multimap<int,vector<pair<size_t,size_t> > >delete_map;

  10. void find_row_min_num(void){
  11.     for(int i=0;i<row;++i){
  12.         vector<int>& tmp_arr = matrix[i];
  13.         int tmp = matrix[i][0];
  14.         int k = 0;
  15.         for(int j=0;j<col;++j){
  16.             if(tmp > tmp_arr[j]){
  17.                 tmp = tmp_arr[j];
  18.                 k = j;
  19.             }
  20.         }
  21.         mark[i][k] = true;
  22.         //min_num.insert(make_pair(tmp,i*row+k));
  23.     }
  24. }

  25. void find_col_min_num(void){
  26.     for(int j=0;j<col;++j){
  27.         int tmp = matrix[0][j];
  28.         int k = 0;
  29.         for(int i=0;i<row;++i){
  30.             if(tmp > matrix[i][j]){
  31.                 tmp = matrix[i][j];
  32.                 k = i;
  33.             }
  34.         }
  35.         if(false == mark[k][j]){
  36.             mark[k][j] = true;
  37.             //min_num.insert(make_pair(tmp,k*row+j));
  38.         }
  39.     }
  40. }
  41. void mark_fix(int i,int pre){
  42.     //首先检查是否可以直接删除
  43.     for(int k=0;k<row;++k){
  44.         if(mark[k][pre] && k != i){
  45.             mark[i][pre] = false;
  46.             return;
  47.         }
  48.     }

  49.     for(int ii=i+1;ii<row;++ii){
  50.         if(mark[ii][pre])
  51.             continue;
  52.         if(matrix[ii][pre] == matrix[i][pre]){//同一列中有相同的最小值
  53.             for(int jj=0;jj<col;++jj){
  54.                 if(mark[ii][jj]){
  55.                     for(int iii=0;iii<row;++iii){//看看栓出此列是否合法
  56.                         if(mark[iii][jj]){
  57.                             if(iii != ii){
  58.                                 mark[ii][jj] = false;
  59.                                 mark[i][pre] = false;
  60.                                 mark[ii][pre] = true;
  61.                                 return;
  62.                             }
  63.                         }
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.     }
  69. }

  70. void check_row(void){
  71.     for(int i=0;i<row;++i){
  72.         int pre = -1;
  73.         for(int j=0;j<col;++j){
  74.             if(mark[i][j]){
  75.                 if(-1 != pre){
  76.                     mark_fix(i,pre);
  77.                 }
  78.                 pre = j;
  79.             }
  80.         }
  81.         int count =0;
  82.         for(int k=0;k<col;++k){
  83.             if(mark[i][k])
  84.                 ++count;
  85.         }
  86.         if(count>1)
  87.             mark_fix(i,pre);
  88.     }
  89. }
  90. void delete_elem(void){
  91.     check_row();
  92. }
  93. void check_row_and_col(void){
  94.     for(int i=0;i<row;++i){
  95.         bool b = false;
  96.         for(int j=0;j<col;++j){
  97.             if(mark[i][j])
  98.                 if(!b)
  99.                     b = true;
  100.                 else{
  101.                     m_row.push_back(i);
  102.                     break;
  103.                 }
  104.         }
  105.     }
  106.     
  107.     for(int i=0;i<col;++i){
  108.         bool b = false;
  109.         for(int j=0;j<row;++j){
  110.             if(mark[j][i])
  111.                 if(!b)
  112.                     b = true;
  113.                 else{
  114.                     m_col.push_back(i);
  115.                     break;
  116.                 }
  117.         }
  118.     }
  119. }
  120. void fix_matrix(void){
  121.     check_row_and_col();
  122.     if(m_row.empty() || m_col.empty())
  123.         return;
  124.     for(size_t i=0;i<m_row.size();++i){
  125.         int max_num = 0;
  126.         int tmp_row = m_row[i];
  127.         vector<pair<size_t,size_t> > pairs;
  128.         for(int k=0;k<col;++k){
  129.             if(mark[tmp_row][k]){
  130.                 int tmp = matrix[tmp_row][k];
  131.                 for(size_t j=0;j<m_col.size();++j){
  132.                     int tmp_col = m_col[j];
  133.                     for(int kk=0;kk<row;++kk){
  134.                         if(mark[kk][tmp_col]){
  135.                             if(kk!=tmp_row && k!=tmp_col){
  136.                                 int a1 = matrix[kk][k];
  137.                                 int a2 = matrix[tmp_row][k];
  138.                                 int a3 = matrix[kk][tmp_col];
  139.                                 if(a1< a2+a3 && a2+a3-a1 > max_num){
  140.                                     max_num = a2+a3-a1;
  141.                                     pairs.clear();
  142.                                     pairs.push_back(make_pair(tmp_row,k));
  143.                                     pairs.push_back(make_pair(kk,tmp_col));
  144.                                 }
  145.                             }
  146.                         }
  147.                     }
  148.                 }
  149.             }
  150.         }
  151.         if(!pairs.empty())
  152.             delete_map.insert(make_pair(max_num,pairs));
  153.     }
  154. }
  155. bool adjust_elem(void){
  156.     if(delete_map.empty()){
  157.         delete_elem();
  158.         return true;
  159.     }
  160.     else{
  161.         for(multimap<int,vector<pair<size_t,size_t> > >::reverse_iterator riter = delete_map.rbegin();
  162.             riter != delete_map.rend();++riter){
  163.                 vector<pair<size_t,size_t> > tmp= riter->second;
  164.                 size_t a1 = tmp[0].first;
  165.                 size_t a2 = tmp[0].second;
  166.                 size_t a3 = tmp[1].first;
  167.                 size_t a4 = tmp[1].second;
  168.                 if(mark[a1][a4])
  169.                     if(matrix[a1][a2]+matrix[a3][a4]-matrix[a3][a2]<matrix[a1][a4]){
  170.                         mark[a1][a4] = false;
  171.                         continue;
  172.                     }
  173.                 if(mark[a1][a2] && mark[a3][a4]){
  174.                     mark[a1][a2] = mark[a3][a4] = false;
  175.                     mark[a3][a2] =true;
  176.                 }
  177.         }
  178.         delete_map.clear();
  179.         m_row.clear();
  180.         m_col.clear();
  181.         return false;
  182.     }
  183. }
  184. void find_min_sum(){
  185.     find_row_min_num();
  186.     find_col_min_num();

  187.     bool b = false;
  188.     while(!b){
  189.         fix_matrix();
  190.         b = adjust_elem();
  191.     }
  192. }
  193. int every_group(void){
  194.     cin>>row>>col;
  195.     for(int i=0;i<row;++i){
  196.         vector<int>tmp_arr;
  197.         vector<bool>tmp_mark;
  198.         for(int j=0;j<col;++j){
  199.             int tmp=0;
  200.             cin>>tmp;
  201.             tmp_arr.push_back(tmp);
  202.             tmp_mark.push_back(false);
  203.         }
  204.         matrix.push_back(tmp_arr);
  205.         mark.push_back(tmp_mark);
  206.     }

  207.     find_min_sum();

  208.     int sum=0;
  209.     for(int i=0;i<row;++i){
  210.         for(int j=0;j<col;++j){
  211.             if(true == mark[i][j]){
  212.                 sum += matrix[i][j];
  213.             }
  214.         }
  215.     }
  216.     matrix.clear();
  217.     mark.clear();
  218.     m_row.clear();
  219.     m_col.clear();
  220.     row=col=0;
  221.     return sum;
  222. }
  223. int main(){
  224.     int group_num;
  225.     cin>>group_num;
  226.     vector<int> vec;
  227.     for(int i=0;i<group_num;++i)
  228.         vec.push_back(every_group());

  229.     for(size_t i=0;i< vec.size();++i){
  230.         std::cout<<"Case "<<i+1<<": "<<vec[i]<<endl;
  231.     }

  232.     return 0;
  233. }

阅读(3995) | 评论(2) | 转发(0) |
给主人留下些什么吧!~~

bl竹子2014-04-16 10:34:15

hilcj0001:Hello度娘上搜到po主的
你这个方法我也想过了,不过还是不行的。
看下面这组数据,正确结果应该是选10 11 10 11 10=52,你的代码输出55。
10 99 99 99 99 
99 10 99 11 99
99 99 10 10 10
99 11 10 15 99
99 99 10 99 15

嗯,问题出在我的变换上了,我只对那些同行和同列存在多余一个元素的上,并没有进行全局调整,呵呵。贪心算法吗,很难得到最优解的(据说可以通过拟阵证明,但我是一直没看懂啊)当时提交,就AC了

回复 | 举报

hilcj00012014-04-16 10:08:27

Hello度娘上搜到po主的
你这个方法我也想过了,不过还是不行的。
看下面这组数据,正确结果应该是选10 11 10 11 10=52,你的代码输出55。
10 99 99 99 99 
99 10 99 11 99
99 99 10 10 10
99 11 10 15 99
99 99 10 99 15