Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define sz 50
- #define llf long long
- #define inf 10000000
- using namespace std ;
- llf best_soln = inf ;
- class Returned
- {
- public:
- vector <llf> rs ; // index of subsets
- vector <llf>mk ; //mark of elements(taken or not)
- };
- vector <llf> v ;//universe
- vector <llf> s[sz] ;//array of subsets
- //vector <llf > frs;
- Returned foo (llf i, llf ln,Returned r)
- {
- Returned frt, frt1, frt2;
- llf j ;
- frt = r ;
- llf r_rs_ln = r.rs.size() ;
- llf r_mk_ln = r.mk.size() ;
- llf covered1 = 0, covered2 = 0;
- if (i==ln)
- {
- return frt;
- }
- llf mx =-1,cnt = 0;
- //find cardinality
- for (j = i ; j<ln ; j++)
- {
- llf si = s[j].size() ;
- mx= max(mx,si) ;
- }
- //number of elements not covered
- for (j = 0 ; j<r_mk_ln ; j++)
- {
- if (r.mk[j]==0)
- {
- cnt++ ;
- }
- }
- double xtra =(double)cnt/(double)mx ;
- llf lowerbound = r.rs.size()+ceil(xtra) ;
- if (lowerbound<best_soln)
- {
- frt1 = r ;
- frt2 = r ;
- llf subset_ln= s[i].size() ;
- for (j = 0; j< subset_ln ; j++)
- {
- frt1.mk[s[i][j]-1] = 1 ;
- }
- frt1.rs.push_back(i) ;
- frt1 = foo (i+1,ln,frt1) ;
- frt2= foo (i+1,ln,frt2) ;
- llf mark_ln1= frt1.mk.size() ;
- llf mark_ln2= frt2.mk.size() ;
- for (j = 0; j< mark_ln1 ; j++)
- {
- if (frt1.mk[j]==0)
- {
- break ;
- }
- }
- if (j==mark_ln1)
- {
- covered1 = 1;
- }
- for (j = 0; j< mark_ln2 ; j++)
- {
- if (frt2.mk[j]==0)
- {
- break ;
- }
- }
- if (j==mark_ln2)
- {
- covered2 = 1;
- }
- if (covered2==0&&covered1==1)
- {
- frt = frt1 ;
- best_soln =frt.rs.size();
- }
- else if (covered1==0&&covered2==1)
- {
- frt = frt2 ;
- best_soln =frt.rs.size();
- }
- else if (covered1==1&&covered2==1)
- {
- if (frt1.rs.size()<frt2.rs.size())
- {
- frt = frt1 ;
- }
- else
- {
- frt = frt2 ;
- }
- best_soln =frt.rs.size();
- }
- return frt ;
- }
- }
- int main ()
- {
- //freopen ("o.txt","w",stdout) ;
- llf n, m, i, j, k;
- cin >> n >> m;
- for (i = 0; i < n ; i++)
- {
- v.push_back(i+1) ;
- }
- //subset s[m] ;
- char temp ;
- for (i = 0 ; i < m ; i++)
- {
- do
- {
- scanf("%I64d%c", &k, &temp);
- //cout << k << ",";
- s[i].push_back(k) ;
- }
- while(temp!= '\n');
- }
- // for (i = 0 ; i < m ; i++)
- // {
- // cout << s[i].size()<< endl ;
- // for (j = 0 ; j < s[i].size() ; j++)
- // {
- // cout<< s[i][j] << " ";
- // }
- //
- // cout << endl ;
- // }
- Returned res ;
- //initialize
- for (j = 0; j<n ; j++)
- {
- res.mk.push_back(0) ;
- }
- res = foo (0,m,res) ;
- //cout << "printing"<< endl ;
- //printing indexes of subsets
- llf no_of_subsets = res.rs.size() ;
- if (no_of_subsets == 0)
- {
- cout << "No Solution"<< endl ;
- return 0 ;
- }
- cout << no_of_subsets<< endl ;
- for (i = 0 ; i < no_of_subsets ; i++)
- {
- llf subset_size = s[res.rs[i]].size() ;
- llf subset_index = res.rs[i] ;
- for (j= 0 ; j < subset_size ; j++)
- {
- cout << s[subset_index][j] << " ";
- }
- cout << endl ;
- }
- return 0 ;
- }
Advertisement
Add Comment
Please, Sign In to add comment