Advertisement
Guest User

Untitled

a guest
Apr 29th, 2016
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define _in(kkk) 2*(kkk) - 1
  3. #define _out(kkk) 2*(kkk)
  4.  
  5. using namespace std;
  6.  
  7. typedef unsigned long long int llu;
  8.  
  9. vector<vector<llu> > res;
  10. llu mf, f, s, t, k, m, size;
  11. vector<llu> parent;
  12.  
  13. void augument(llu v, llu minEdge)
  14. {
  15.   if(v == s)
  16.   {
  17.     f = minEdge;
  18.     return;
  19.   }
  20.   if(parent[v] != -1) {
  21.     augument(parent[v], min(minEdge, res[parent[v]][v]));
  22.     res[parent[v]][v] -= f;
  23.     res[v][parent[v]] += f;
  24.   }
  25. }
  26.  
  27. void init(const vector<llu>& a, const vector<llu>& b)
  28. {
  29.   size = 2*(a.size() + b.size()) + 2;
  30.   res.assign(size, vector<llu>(size, 0));
  31.   for(llu i = 1; i <= a.size(); ++i)
  32.     res[_in(i)][_out(i)] = 1;
  33.   for(llu i = 1; i <= b.size(); ++i)
  34.     res[_in(a.size() + i)][_out(a.size() + i)] = 1;
  35.   for(llu i = 1; i <= a.size(); ++i)
  36.   for(llu j = 1; j <= b.size(); ++j)
  37.     if(max(a[i-1], b[j-1]) - min(a[i-1], b[j-1]) < k)
  38.       res[_out(i)][_in(a.size() + j)] = res[_out(a.size() + j)][_in(i)] = 1;
  39.   s = 0; t = size - 1;
  40.   for(llu i = 1; i <= m; ++i)
  41.     res[s][_in(i)] = 1;
  42.   for(llu i = a.size() + b.size(); i > a.size() + b.size() - m; --i)
  43.     res[_out(i)][t] = 1;
  44. }
  45.  
  46. llu maxFlow(const vector<llu>& a, const vector<llu>& b)
  47. {
  48.   init(a,b);
  49.   mf = 0;
  50.   while(1)
  51.   {
  52.     f = 0;
  53.     vector<bool> saw(size, false);
  54.     queue<llu> fila;
  55.     saw[s] = true; fila.push(s);
  56.     parent.assign(size, -1);
  57.     while(!fila.empty())
  58.     {
  59.       llu u = fila.front(); fila.pop();
  60.       if(u == t) break;
  61.       for(llu v = 0; v < size; ++v)
  62.         if(res[u][v] && !saw[v])
  63.         {
  64.           saw[v] = true;
  65.           fila.push(v);
  66.           parent[v] = u;
  67.         }
  68.     }
  69.     augument(t, ULLONG_MAX);
  70.     if(!f) break;
  71.     mf += f;
  72.   }
  73.   return mf;
  74. }
  75.  
  76. int main()
  77. {
  78.   llu na, nb;
  79.   scanf("%llu %llu %llu %llu", &m, &na, &nb, &k);
  80.   vector<llu> a(na), b(nb);
  81.   for(llu i = 0; i < na; ++i)
  82.     scanf("%llu", &a[i]);
  83.   for(llu i = 0; i < nb; ++i)
  84.     scanf("%llu", &b[i]);
  85.   sort(b.rbegin(), b.rend());
  86.   sort(a.rbegin(), a.rend());
  87.   llu an = maxFlow(a,b);
  88.   if(an < m)
  89.     an = maxFlow(b,a);
  90.   if(an >= m)
  91.     puts("S");
  92.   else
  93.     puts("N");
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement