fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using int64 = long long;
  5. const int64 NEG = -(1LL<<60);
  6.  
  7. int main() {
  8.     ios::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.  
  11.     int n, m;
  12.     if (!(cin >> n >> m)) return 0;
  13.     vector<int64> c(n);
  14.     for (int i = 0; i < n; ++i) cin >> c[i];
  15.  
  16.     // adjacency on full graph (n <= 64 is safe with 64-bit mask)
  17.     vector<unsigned long long> adj(n, 0);
  18.     for (int i = 0, u, v; i < m; ++i) {
  19.         cin >> u >> v; --u; --v;
  20.         adj[u] |= (1ULL << v);
  21.         adj[v] |= (1ULL << u);
  22.     }
  23.  
  24.     int n1 = n / 2;
  25.     int n2 = n - n1;
  26.  
  27.     // masks limited to their halves
  28.     const unsigned long long FULLA64 = (n1 == 64 ? ~0ULL : ((1ULL << n1) - 1ULL));
  29.     const unsigned long long FULLB64 = (n2 == 64 ? ~0ULL : ((1ULL << n2) - 1ULL));
  30.  
  31.     // Data for A
  32.     vector<int64> wA(n1);
  33.     vector<unsigned int> inA(n1, 0); // adjacency inside A (n1 bits)
  34.     for (int i = 0; i < n1; ++i) {
  35.         wA[i] = c[i];
  36.         inA[i] = (unsigned int)(adj[i] & FULLA64);
  37.     }
  38.  
  39.     // Data for B
  40.     vector<int64> wB(n2);
  41.     vector<unsigned int> inB(n2, 0);        // adjacency inside B (n2 bits)
  42.     vector<unsigned int> crossBA(n2, 0);    // from B vertex -> forbidden A bits
  43.     for (int j = 0; j < n2; ++j) {
  44.         int v = n1 + j;
  45.         wB[j] = c[v];
  46.         inB[j] = (unsigned int)((adj[v] >> n1) & FULLB64);
  47.         crossBA[j] = (unsigned int)(adj[v] & FULLA64);
  48.     }
  49.  
  50.     // DP on side A for independent sets, then SOS to get bestA[allowMask]
  51.     int sizeA = 1 << n1;
  52.     vector<int64> dpA(sizeA, NEG);
  53.     dpA[0] = 0;
  54.     for (int mask = 1; mask < sizeA; ++mask) {
  55.         int u = __builtin_ctz(mask);
  56.         int pm = mask ^ (1 << u);
  57.         if (dpA[pm] == NEG) continue;
  58.         if ((inA[u] & pm) == 0) dpA[mask] = dpA[pm] + wA[u];
  59.     }
  60.     vector<int64> bestA = dpA; // max over submasks
  61.     for (int i = 0; i < n1; ++i)
  62.         for (int mask = 0; mask < sizeA; ++mask)
  63.             if (mask & (1 << i))
  64.                 bestA[mask] = max(bestA[mask], bestA[mask ^ (1 << i)]);
  65.  
  66.     // Enumerate B subsets, keep only independent ones
  67.     int sizeB = 1 << n2;
  68.     auto indep_and_sum_B = [&](int mask)->pair<bool,int64>{
  69.         int tmp = mask;
  70.         int64 sum = 0;
  71.         while (tmp) {
  72.             int v = __builtin_ctz(tmp);
  73.             tmp ^= (1 << v);
  74.             if (inB[v] & tmp) return {false, 0};
  75.             sum += wB[v];
  76.         }
  77.         return {true, sum};
  78.     };
  79.  
  80.     int64 ans = 0;
  81.     for (int mask = 0; mask < sizeB; ++mask) {
  82.         auto [ok, sumB] = indep_and_sum_B(mask);
  83.         if (!ok) continue;
  84.         unsigned int forbidA = 0;
  85.         int tmp = mask;
  86.         while (tmp) {
  87.             int v = __builtin_ctz(tmp);
  88.             tmp ^= (1 << v);
  89.             forbidA |= crossBA[v];
  90.         }
  91.         int allowA = ((1 << n1) - 1) & ~((int)forbidA);
  92.         ans = max(ans, sumB + bestA[allowA]);
  93.     }
  94.  
  95.     cout << ans << '\n';
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
4 2
4 9 2 1
1 4
2 4
stdout
copy 
15
https://ideone.com/kJaSKk
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!