SHARE
TWEET

Untitled

a guest May 25th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define sz(x) ((int)x.size ())
  6.  
  7. const int N = 2000;
  8. const int inf = 1e9 + 7;
  9.  
  10. int used[N], in[N], w[N];
  11.  
  12. int timer = 1;
  13. vector<int> g[N];
  14. int was[N], s, t;
  15.  
  16. struct edge {
  17.     int fr, to, f;
  18. };
  19.  
  20. vector<edge> e;
  21.  
  22. void make (int a, int b, int c) {
  23.     g[a].push_back(sz(e));
  24.     e.push_back({a, b, c});
  25.     g[b].push_back(sz(e));
  26.     e.push_back({b, a, 0});
  27. }                  
  28.  
  29. int go (int v, int flow = inf) {
  30.     was[v] = timer;
  31.     if (v == t) return flow;
  32.     for (auto i : g[v])
  33.         if (e[i].f && was[e[i].to] != timer) {
  34.             int push = go (e[i].to, min (flow, e[i].f));
  35.             if (push) {
  36.                 e[i].f -= push;
  37.                 e[i^1].f += push;
  38.                 return push;
  39.             }
  40.         }
  41.     return 0;
  42. }
  43.  
  44. void dfs (int v, int c, vector<vector<int>>& gr, vector<int>& A, vector<int>& B) {
  45.     used[v] = 1 + c;
  46.     if (!c) A.push_back(v);
  47.     else B.push_back(v);
  48.     for (auto x : gr[v])
  49.         if (used[x] == 0)
  50.             dfs (x, c ^ 1, gr, A, B);
  51. }
  52.  
  53. vector<int> get (vector<int>& p, vector<int>& A, int pos, vector<vector<int>>& gr) {
  54.     vector<int> ans(sz(A));
  55.     for (int i = 0; i < sz(A); i++) {
  56.         for (auto x : gr[A[i]])
  57.             if (w[x] >= 0 && p[w[x]] == pos)
  58.                 ans[i] = 1;
  59.     }
  60.     return ans;
  61. }
  62.  
  63. bool go (int pos, vector<int>& p, vector<int>& ans, vector<vector<int>>& gr, int n, vector<int>& S, vector<int>& A, vector<int>& B) {  
  64.     if (pos == sz(p)) {
  65.         int ok = 0;
  66.         vector<int> T;
  67.         int k = sz(p);
  68.         for (int i = 0; i < k; i++) {
  69.             in[S[i]] = (p[i] == 1);
  70.             if (p[i] == 2) T.push_back(S[i]);
  71.         }
  72.         for (int i = 0; i < k; i++) {
  73.             if (p[i] == 0)
  74.                 for (auto x : gr[S[i]])
  75.                     ok |= in[x];
  76.         }
  77.         if (ok) return false;
  78.         auto Al = get (p, A, 0, gr);
  79.         auto Ar = get (p, A, 1, gr);
  80.         auto Bl = get (p, B, 0, gr);
  81.         auto Br = get (p, B, 1, gr);
  82.         vector<int> AlBr, ArBl;
  83.         for (int i = 0; i < sz(A); i++) {
  84.             if (Al[i]) AlBr.push_back(A[i]);
  85.             if (Ar[i]) ArBl.push_back(A[i]);
  86.         }
  87.         for (int i = 0; i < sz(B); i++) {
  88.             if (Br[i]) AlBr.push_back(B[i]);
  89.             if (Bl[i]) ArBl.push_back(B[i]);
  90.         }
  91.         e.clear();
  92.         s = 2 * n;
  93.         t = s + 1;
  94.         for (int i = 0; i <= t; i++) g[i].clear();
  95.         for (int i = 0; i < n; i++)
  96.             if (used[i] != -1) {
  97.                 make (i, n + i, 1);
  98.                 for (auto x : gr[i])
  99.                     if (used[x] != -1)
  100.                         make (n + i, x, 1);
  101.             }
  102.         for (auto x : AlBr) make (s, x, 1);
  103.         for (auto x : ArBl) make (x + n, t, 1);
  104.         timer++;
  105.         int flow = 0;
  106.         int cur;
  107.         while (cur = go(s)) {
  108.             flow += cur;
  109.             timer++;
  110.             if (flow >= sz(S) - sz(T)) break;
  111.         }
  112.         if (flow < sz(S) - sz(T)) {
  113.             for (int i = 0; i < sz(e); i += 2)
  114.                 if (e[i].fr == s && !e[i].f) ans.push_back(e[i].to);
  115.             for (auto x : T) ans.push_back(x);
  116.             return true;
  117.         }
  118.         return false;
  119.     }
  120.     for (int i = 0; i < 3; i++) {
  121.         p[pos] = i;
  122.         if (go (pos + 1, p, ans, gr, n, S, A, B)) return true; 
  123.     }
  124.     return false;
  125. }
  126.  
  127. bool solve (int n, vector<vector<int>>& gr, vector<int>& s) {
  128.     memset (w, -1, sizeof(w[0]) * n);
  129.     memset (used, 0, sizeof(used[0]) * n);
  130.     memset (in, 0, sizeof(in[0]) * n);
  131.     vector<int> A, B;
  132.     int k = sz(s);
  133.     vector<int> t(k);  
  134.     for (int i = 0; i < k; i++)
  135.         used[s[i]] = -1, w[s[i]] = i;
  136.     for (int i = 0; i < n; i++)
  137.         if (used[i] == 0)
  138.             dfs (i, 0, gr, A, B);
  139.     vector<int> ans;
  140.     if (go (0, t, ans, gr, n, s, A, B)) {
  141. //      for (auto x : ans) cout << x + 1 << " ! ";
  142.         return true;
  143.     } //else cout << "No";
  144.     return false;
  145. }
  146.  
  147. bool tunec (int n, vector<vector<int>>& g, int k, vector<int>& ans) {
  148.     if (n - 1 <= k) {
  149.         for (int i = 0; i < k; i++)
  150.             ans.push_back(i);
  151.         return true;
  152.     }
  153.     vector<int> s(k + 1);
  154.     for (int i = 0; i <= k; i++) s[i] = i;
  155.     vector<vector<int>> gr(n);
  156.     for (int i = 0; i < k; i++)
  157.         for (auto x : g[i])
  158.             if (x < i) {
  159.                 gr[i].push_back(x);
  160.                 gr[x].push_back(i);
  161.             }
  162.     for (int i = k; i < n; i++) {
  163.         for (auto x : g[i])
  164.             if (x < i) {
  165.                 gr[i].push_back(x);
  166.                 gr[x].push_back(i);
  167.             }
  168.         if (sz(s) <= k)  {
  169.             if (i != n - 1) s.push_back(i + 1);
  170.             continue;
  171.         }
  172.         vector<int> x;
  173.         auto ok = solve (i + 1, gr, s);
  174.         if (!ok) break;
  175.         if (i != n - 1) x.push_back(i + 1);
  176.         s = x;     
  177.     }
  178.     if (sz(s) <= k) {
  179.         ans = s;
  180.         return true;
  181.     }
  182.     return false;
  183. }
  184.  
  185. int main() {
  186.     int n, m, k;
  187.     cin >> n >> m >> k;
  188.     vector<vector<int>> gr(n);
  189.     for (int i = 0; i < m; i++) {
  190.         int x, y;
  191.         cin >> x >> y;
  192.         x--; y--;
  193.         gr[x].push_back(y);
  194.         gr[y].push_back(x);
  195.     }
  196.     vector<int> ans;
  197.     if (tunec (n, gr, k, ans))
  198.         for (auto x : ans) cout << x + 1 << " ";
  199.     else cout << "No solution";        
  200. }
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
 
Top