shamiul93

Untitled

Jan 23rd, 2018
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define sz 50
  3. #define llf long long
  4. #define inf 10000000
  5. using namespace std ;
  6. llf best_soln = inf ;
  7.  
  8. class Returned
  9. {
  10. public:
  11.     vector <llf> rs ; // index of subsets
  12.     vector <llf>mk ; //mark of elements(taken or not)
  13.  
  14. };
  15. vector <llf> v ;//universe
  16. vector <llf> s[sz] ;//array of subsets
  17. //vector <llf > frs;
  18. Returned foo (llf i, llf ln,Returned r)
  19. {
  20.     Returned frt, frt1, frt2;
  21.     llf j ;
  22.     frt = r ;
  23.     llf r_rs_ln = r.rs.size() ;
  24.     llf r_mk_ln = r.mk.size() ;
  25.     llf covered1 = 0, covered2  = 0;
  26.  
  27.     if (i==ln)
  28.     {
  29.         return frt;
  30.     }
  31.  
  32.     llf mx =-1,cnt = 0;
  33.  
  34.     //find cardinality
  35.     for (j = i ; j<ln ; j++)
  36.     {
  37.         llf si = s[j].size() ;
  38.         mx= max(mx,si) ;
  39.     }
  40.  
  41.     //number of elements not covered
  42.     for (j = 0 ; j<r_mk_ln ; j++)
  43.     {
  44.         if (r.mk[j]==0)
  45.         {
  46.             cnt++ ;
  47.         }
  48.  
  49.     }
  50.     double  xtra =(double)cnt/(double)mx ;
  51.  
  52.     llf lowerbound = r.rs.size()+ceil(xtra) ;
  53.  
  54.     if (lowerbound<best_soln)
  55.     {
  56.         frt1 = r ;
  57.         frt2 = r ;
  58.         llf subset_ln= s[i].size() ;
  59.         for (j = 0; j< subset_ln ; j++)
  60.         {
  61.             frt1.mk[s[i][j]-1] = 1 ;
  62.         }
  63.  
  64.  
  65.         frt1.rs.push_back(i) ;
  66.  
  67.         frt1 = foo (i+1,ln,frt1) ;
  68.  
  69.         frt2= foo (i+1,ln,frt2) ;
  70.  
  71.         llf mark_ln1= frt1.mk.size() ;
  72.         llf mark_ln2= frt2.mk.size() ;
  73.  
  74.         for (j = 0; j< mark_ln1 ; j++)
  75.         {
  76.             if (frt1.mk[j]==0)
  77.             {
  78.                 break ;
  79.             }
  80.         }
  81.         if (j==mark_ln1)
  82.         {
  83.             covered1 = 1;
  84.         }
  85.  
  86.         for (j = 0; j< mark_ln2 ; j++)
  87.         {
  88.             if (frt2.mk[j]==0)
  89.             {
  90.                 break ;
  91.             }
  92.         }
  93.         if (j==mark_ln2)
  94.         {
  95.             covered2 = 1;
  96.         }
  97.  
  98.         if (covered2==0&&covered1==1)
  99.         {
  100.             frt = frt1 ;
  101.             best_soln =frt.rs.size();
  102.         }
  103.         else if (covered1==0&&covered2==1)
  104.         {
  105.             frt = frt2 ;
  106.             best_soln =frt.rs.size();
  107.         }
  108.         else if (covered1==1&&covered2==1)
  109.         {
  110.             if (frt1.rs.size()<frt2.rs.size())
  111.             {
  112.                 frt = frt1 ;
  113.             }
  114.  
  115.             else
  116.             {
  117.                 frt = frt2 ;
  118.             }
  119.             best_soln =frt.rs.size();
  120.         }
  121.         return frt ;
  122.     }
  123. }
  124. int main ()
  125. {
  126.  
  127.     //freopen ("o.txt","w",stdout) ;
  128.     llf n, m, i, j, k;
  129.     cin >> n >> m;
  130.     for (i = 0; i < n ; i++)
  131.     {
  132.  
  133.         v.push_back(i+1) ;
  134.     }
  135.     //subset s[m] ;
  136.     char temp ;
  137.     for (i = 0 ; i < m ; i++)
  138.     {
  139.         do
  140.         {
  141.             scanf("%I64d%c", &k, &temp);
  142.             //cout << k << ",";
  143.             s[i].push_back(k) ;
  144.  
  145.         }
  146.         while(temp!= '\n');
  147.     }
  148. //    for (i = 0 ; i < m ; i++)
  149. //    {
  150. //        cout << s[i].size()<< endl ;
  151. //        for (j = 0 ; j < s[i].size() ; j++)
  152. //        {
  153. //            cout<< s[i][j] << " ";
  154. //        }
  155. //
  156. //        cout << endl ;
  157. //    }
  158.  
  159.  
  160.     Returned res ;
  161.     //initialize
  162.     for (j = 0; j<n ; j++)
  163.     {
  164.         res.mk.push_back(0) ;
  165.     }
  166.     res  = foo (0,m,res) ;
  167.     //cout << "printing"<< endl ;
  168.     //printing indexes of subsets
  169.     llf no_of_subsets = res.rs.size() ;
  170.     if (no_of_subsets == 0)
  171.  
  172.     {
  173.         cout << "No Solution"<< endl ;
  174.         return 0 ;
  175.     }
  176.     cout << no_of_subsets<< endl ;
  177.     for (i = 0 ; i < no_of_subsets ; i++)
  178.     {
  179.         llf subset_size = s[res.rs[i]].size() ;
  180.         llf subset_index = res.rs[i] ;
  181.         for (j= 0 ; j < subset_size ; j++)
  182.         {
  183.             cout << s[subset_index][j] << " ";
  184.         }
  185.         cout << endl ;
  186.     }
  187.     return 0 ;
  188. }
Advertisement
Add Comment
Please, Sign In to add comment