SHARE
TWEET

Untitled

a guest Oct 15th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <random>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <map>
  6. #include <set>
  7.  
  8. using namespace std;
  9.  
  10. const int n = 24;
  11.  
  12. vector<int> gr[n + 1];
  13.  
  14. pair<int, int> get_rand_pair() {
  15.     int a = rand() % n + 1;
  16.     int b = rand() % n + 1;
  17.     while (a == b) {
  18.         b = rand() % n + 1;
  19.     }
  20.     return {a, b};
  21. }
  22.  
  23. vector<bool> used(n + 1);
  24. map<pair<int, int>, bool> e;
  25. vector<pair<int, int>> grr;
  26.  
  27. int check() {
  28.     vector<int> ver;
  29.     while (true) {
  30.         int mx = 0;
  31.         int v = -1;
  32.         for (int i = 1; i <= n; ++i) {
  33.             if (!used[i]) {
  34.                 int cnt = 0;
  35.                 for (auto to : gr[i]) {
  36.                     if (!e[{i, to}]) {
  37.                         ++cnt;
  38.                     }
  39.                 }
  40.                 if (cnt > mx) {
  41.                     mx = cnt;
  42.                     v = i;
  43.                 }
  44.             }
  45.         }
  46.         if (v == -1) {
  47.             break;
  48.         }
  49.         ver.push_back(v);
  50.         for (auto to : gr[v]) {
  51.             e[{v, to}] = true;
  52.             e[{to, v}] = true;
  53.         }
  54.     }
  55.     return ver.size();
  56. }
  57.  
  58. int get_bit(int mask, int i) {
  59.     return (mask >> i) & 1;
  60. }
  61.  
  62. int check_long() {
  63.     int SZ = (1 << n);
  64.     int mn = 10;
  65.     for (int mask = 0; mask < SZ; ++mask) {
  66.         int cnt = 0;
  67.         for (auto ee : grr) {
  68.             int a = ee.first;
  69.             int b = ee.second;
  70.             if (!get_bit(mask, a - 1) && !get_bit(mask, b - 1)) {
  71.                 break;
  72.             }
  73.             ++cnt;
  74.         }
  75.         if (cnt == grr.size()) {
  76.             int verts = 0;
  77.             for (int j = 0; j < n; ++j) {
  78.                 if (get_bit(mask, j)) {
  79.                     ++verts;
  80.                 }
  81.             }
  82.             mn = min(mn, verts);
  83.         }
  84.     }
  85.     return mn;
  86. }
  87.  
  88. int main() {
  89.     std::ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  90.     while (true) {
  91.         for (int i = 1; i <= n; ++i) {
  92.             gr[i].clear();
  93.         }
  94.         grr.clear();
  95.         for (int i = 1; i <= n; ++i) {
  96.             for (int j = 1; j <= n; ++j) {
  97.                 e[{i, j}] = e[{j, i}] = false;
  98.             }
  99.         }
  100.         int m = rand() % (n * (n - 1) / 2);
  101.         set<pair<int, int>> s;
  102.         while (m--) {
  103.             auto p = get_rand_pair();
  104.             while (s.find(p) != s.end()) {
  105.                 p = get_rand_pair();
  106.             }
  107.             s.insert(p);
  108.             s.insert({p.second, p.first});
  109.             grr.push_back(p);
  110.             gr[p.first].push_back(p.second);
  111.             gr[p.second].push_back(p.first);
  112.         }
  113.         int greedy = check();
  114.         int ans = check_long();
  115.         if (greedy > ans * 2) {
  116.             cout << greedy << " " << ans << endl;
  117.             vector<vector<int>> dist(n + 1, vector<int> (n + 1));
  118.             for (int i = 1; i <= n; ++i) {
  119.                 cout << i << " : ";
  120.                 for (auto to : gr[i]) {
  121.                     cout << to << " ";
  122.                 }
  123.                 cout << endl;
  124.             }
  125.             exit(0);
  126.         }
  127.         cout << greedy << " " << ans << endl;
  128.     }
  129.     return 0;
  130. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top