Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define f first
  7. #define s second
  8. #define mp make_pair
  9. #define ll long long
  10.  
  11. #define MAXN 200005
  12. #define INF 1000000009
  13. #define MOD 1000000007
  14.  
  15.  
  16. list < set < int > > kerbosh(vector < vector <bool> > a,int SIZE){
  17. set <int> M,G,K,P;
  18. list<set<int> > REZULT;
  19. for (int i=0; i<SIZE;i++)
  20. {
  21. K.insert(i);
  22. }
  23. int v,Count=0,cnt=0;
  24. int Stack1[100];
  25. std::set<int> Stack2[100];
  26. std::set<int>::iterator theIterator;
  27. theIterator=K.begin();
  28.  
  29. auto t = clock();
  30. auto pre = t;
  31. while ((K.size()!=0)||(M.size()!=0))
  32. {
  33. if(clock() - t > 10000000){
  34. cerr << (clock() - t) / 1000000 << " " << (clock() - pre) / 1000000 << " " << v << endl;
  35. t = clock();
  36. if(clock() - pre > 1000000 * 20)
  37. return REZULT;
  38. }
  39.  
  40. if (K.size()!=0)
  41. {
  42. theIterator=K.begin();
  43. v=*theIterator;
  44. Stack2[++Count]=M;
  45. Stack2[++Count]=K;
  46. Stack2[++Count]=P;
  47. Stack1[++cnt]=v;
  48. M.insert(v);
  49. for (int i=0;i<SIZE;i++)
  50. {
  51. if (a[v][i])
  52. {
  53. theIterator=K.find(i);
  54. if (theIterator!=K.end())
  55. {
  56. K.erase(theIterator);
  57. }
  58. theIterator=P.find(i);
  59. if (theIterator!=P.end())
  60. {
  61. P.erase(theIterator);
  62. }
  63. }
  64. }
  65. theIterator=K.find(v);
  66. if (theIterator!=K.end())
  67. {
  68. K.erase(theIterator);
  69. }
  70. }
  71. else
  72. {
  73. if (P.size()==0)
  74. {
  75. REZULT.push_back(M);
  76. }
  77. v=Stack1[cnt--];
  78. P=Stack2[Count--];
  79. K=Stack2[Count--];
  80. M=Stack2[Count--];
  81. theIterator=K.find(v);
  82. if (theIterator!=K.end())
  83. {
  84. K.erase(theIterator);
  85. }
  86. P.insert(v);
  87. }
  88. }
  89. return REZULT;
  90. }
  91.  
  92. void solve(){
  93. vector < vector <int> > gr;
  94. int n, m; // число аудиторий, число мероприятий
  95. cin >> n >> m;
  96.  
  97. vector <vector <int>> v;
  98. v.resize(m);
  99. for(int i = 0; i < m; i++){
  100. int c;
  101. cin >> c;
  102. for(int j = 0; j < c; j++){
  103. int a;
  104. cin >> a;
  105. v[i].pb(a);
  106. }
  107. }
  108.  
  109. gr.clear();
  110. gr.resize(m+1);
  111.  
  112. for(int i = 0; i < m; i++){
  113. cerr << i << " ";
  114. for(int j = i+1; j < m; j++){
  115. set <int> a;
  116. for(auto x: v[i])
  117. a.insert(x);
  118.  
  119. bool y = 1;
  120. for(auto x: v[j])
  121. if(a.find(x) != a.end())
  122. y = 0;
  123.  
  124. if(y){
  125. gr[i+1].pb(j+1);
  126. gr[j+1].pb(i+1);
  127. }
  128. }
  129. }
  130.  
  131. cerr << endl << gr.size() << " gr:\n";
  132. for(int i = 0; i < gr.size(); i++){
  133. cerr << i << ": ";
  134. for(auto x: gr[i])
  135. cerr << x << " ";
  136. cerr << endl;
  137. }
  138. cerr << endl;
  139.  
  140. vector < vector < bool > > g;
  141. g.resize(gr.size());
  142. for(int i = 0; i < gr.size(); i++){
  143. g[i].resize(gr.size(), 1);
  144. cerr << i << ": ";
  145. for(auto x: gr[i]){
  146. g[i][x] = 0;
  147. cerr << x << " ";
  148. }
  149. cerr << endl;
  150. }
  151.  
  152. cerr << "matrix: \n";
  153. for(int i = 0; i < gr.size(); i++){
  154. for(int j = 0; j < gr.size(); j++)
  155. cerr << g[i][j] << " ";
  156. cerr << endl;
  157. }
  158. cerr << endl;
  159.  
  160. auto ans = kerbosh(g, (int)g.size());
  161. cerr << "ans: \n";
  162. vector < set <int> > mx;
  163. set <int> j;
  164. mx.pb(j);
  165. while(!ans.empty()){
  166. auto out = *(ans.rbegin());
  167. ans.pop_back();
  168.  
  169. cerr << out.size() << ": ";
  170. for(auto x: out)
  171. cerr << x << " ";
  172.  
  173. if(out.size() >= mx[0].size()){
  174. if(out.size() > mx[0].size()) mx.clear();
  175. mx.pb(out);
  176. }
  177. cerr << endl;
  178. }
  179. cerr << endl;
  180.  
  181.  
  182. cerr << "MX.SIZE = " << mx.size() << endl;
  183. int mx_a = 0;
  184. set <int> out;
  185. for(auto x: mx){
  186. int a = 0;
  187. for(auto s: x){
  188. a+= v[s-1].size();
  189. }
  190. if(a > mx_a){
  191. mx_a = a;
  192. out = x;
  193. }
  194. }
  195.  
  196. cout << out.size() << endl;
  197. for(auto x: out)
  198. cout << x << " ";
  199. cout << endl;
  200. }
  201.  
  202. int main(){
  203. ios_base::sync_with_stdio(0);
  204. cin.tie(0);
  205. cout.tie(0);
  206.  
  207. int tests = 1;
  208.  
  209. #ifdef LOCAL
  210. bool a;
  211. a = freopen("in.data", "r", stdin);
  212. a = freopen("out.data", "w", stdout);
  213. cin >> tests;
  214. #endif
  215.  
  216. for(int i = 1; i <= tests; i++){
  217. cerr << "TEST " << i << endl;
  218. solve();
  219. }
  220.  
  221. cerr << "End of program";
  222.  
  223. return 0;
  224. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement