Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 29th, 2020 156 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <unordered_map>
  5. #include <algorithm>
  6. #include <string>
  7. #include <unordered_set>
  8. #include <functional>
  9. #include <queue>
  10. #include <vector>
  11. #include <list>
  12. #include <map>
  13. #include <queue>
  14. #include <iomanip>
  15.  
  16. #define mp make_pair
  17. #define i64 long long;
  18. #define ui64 unsigned long long;
  19.  
  20. using namespace std;
  21.  
  22.  
  23. struct Edge {
  24.     int ind;
  25.     int from;
  26.     int to;
  27.     int c;
  28.     int f = 0;
  29.     int back_edge;
  30. };
  31.  
  32. vector<vector<Edge>> g;
  33.  
  34. int n, m, k, s, t;
  35.  
  36. vector<bool> was;
  37.  
  38. int dfs(int v, int flow, int konec) {
  39.     if (v == konec) {
  40.         return flow;
  41.     }
  42.  
  43.     if (v / n > konec / n) {
  44.         return 0;
  45.     }
  46.  
  47.     was[v] = true;
  48.     for (int i = 0; i < g[v].size(); ++i) {
  49.         auto* e = &g[v][i];
  50.         int to = -1;
  51.         if (e->to == v) {
  52.             to = e->from;
  53.             if (!was[to] && e->f < e->c) {
  54.                 int del = dfs(to, min(flow, e->c - e->f), konec);
  55.                 if (del > 0) {
  56.                     e->f += del;
  57.                     g[to][e->back_edge].f -= del;
  58.                     return del;
  59.                 }
  60.             }
  61.         }
  62.         else {
  63.             to = e->to;
  64.             if (!was[to] && e->f < e->c) {
  65.                 int del = dfs(to, min(flow, e->c - e->f), konec);
  66.                 if (del > 0) {
  67.                     e->f += del;
  68.                     g[to][e->back_edge].f -= del;
  69.                     return del;
  70.                 }
  71.             }
  72.         }
  73.     }
  74.  
  75.     return 0;
  76. }
  77.  
  78. vector<bool> www;
  79. vector<vector<int>> g1;
  80. int bfs(int v) {
  81.     queue<pair<int, int>> q;
  82.     q.push(mp(v, 0));
  83.     while (!q.empty()) {
  84.         auto pp = q.front();
  85.         q.pop();
  86.         www[pp.first] = true;
  87.         if (pp.first == t) {
  88.             return pp.second;
  89.         }
  90.         for (int i = 0; i < g1[pp.first].size(); ++i) {
  91.             int to = g1[pp.first][i];
  92.             if (!www[to]) {
  93.                 q.push(mp(to, pp.second + 1));
  94.             }
  95.         }
  96.     }
  97. }
  98.  
  99. int N = 0;
  100.  
  101. void build(int len) {
  102.     N = n * (len + k - 1);
  103.     g.resize(N);
  104.     was.resize(N);
  105.     for (int i = 0; i < len + k - 2; ++i) {
  106.         for (int v = 0; v < n; ++v) {
  107.             Edge e;
  108.             e.f = 0;
  109.             e.c = 1e9;
  110.             e.from = v + i * n;
  111.             e.to = v + (i + 1) * n;
  112.             g[e.from].push_back(e);
  113.             e.f = 1e9;
  114.             g[e.to].push_back(e);
  115.             g[e.from].back().back_edge = g[e.to].size() - 1;
  116.             g[e.to].back().back_edge = g[e.from].size() - 1;
  117.             for (int j = 0; j < g1[v].size(); ++j) {
  118.                 Edge e;
  119.                 e.f = 0;
  120.                 e.c = 1;
  121.                 e.from = v + i * n;
  122.                 e.to = g1[v][j] + (i + 1) * n;
  123.                 g[e.from].push_back(e);
  124.                 e.f = 1;
  125.                 g[e.to].push_back(e);
  126.                 g[e.from].back().back_edge = g[e.to].size() - 1;
  127.                 g[e.to].back().back_edge = g[e.from].size() - 1;
  128.             }
  129.         }
  130.     }
  131. }
  132.  
  133.  
  134. int get_max_flow(int s, int en) {
  135.     was.clear();
  136.     was.resize(N);
  137.     auto saved_graph = g;
  138.     while (dfs(s, 1e9, en) > 0) {
  139.         was.clear();
  140.         was.resize(N);
  141.     }
  142.     int res = 0;
  143.     for (int i = 0; i < g[s].size(); ++i) {
  144.         res += g[s][i].f;
  145.     }
  146.     g = saved_graph;
  147.     return res;
  148. }
  149.  
  150. int main() {
  151. #ifdef _KOCH
  152.     freopen("input.txt", "r", stdin);
  153.     // freopen("output3.txt", "w", stdout);
  154. #else
  155.     // freopen("dominoes.in", "r", stdin);
  156.     // freopen("dominoes.out", "w", stdout);
  157. #endif
  158.     cin >> n >> m >> k >> s >> t;
  159.     s--; t--;
  160.     g1.resize(n);
  161.     www.resize(n);
  162.     for (int i = 0; i < m; ++i) {
  163.         int a, b;
  164.         cin >> a >> b;
  165.         a--; b--;
  166.         g1[a].push_back(b);
  167.         g1[b].push_back(a);
  168.     }
  169.  
  170.     int len = bfs(s);
  171.  
  172.     build(len + 1);
  173.  
  174.     int res = len - 1;
  175.     for (int i = 0; k > get_max_flow(s, t + (len + i) *n); ++i) {
  176.         res = len + i;
  177.     }
  178.  
  179.     was.clear();
  180.         was.resize(N);
  181.     res++;
  182.     while (dfs(s, 1e9, t + res * n) > 0) {
  183.         was.clear();
  184.         was.resize(N);
  185.     }
  186.  
  187.     vector < vector<pair<int, int>>> ans(res);
  188.  
  189.     vector<vector<int>> sheep(n);
  190.  
  191.     int id = k;
  192.  
  193.     cout << res << endl;
  194.     for (int l = 0; l < res; ++l) {
  195.         vector<vector<int>> new_sheep(n);
  196.         for (int i = 0; i < n; ++i) {
  197.             int x = i + l*n;
  198.             for (int j = 0; j < g[x].size(); ++j) {
  199.                 if (g[x][j].f == 1 && g[x][j].to % n != i && g[x][j].to != x) {
  200.                     if (!sheep[i].empty()) {
  201.                         ans[l].push_back(mp(sheep[i].back(), (g[x][j].to % n) + 1));
  202.                         new_sheep[g[x][j].to %n].push_back(sheep[i].back());
  203.                         sheep[i].pop_back();
  204.                     }
  205.                     else {
  206.                         if (id <= 0) {
  207.                             continue;
  208.                         }
  209.                         new_sheep[g[x][j].to % n].push_back(id--);
  210.                         ans[l].push_back(mp(id + 1, (g[x][j].to % n) + 1));
  211.                     }
  212.                 }
  213.             }
  214.         }
  215.         sheep = new_sheep;
  216.     }
  217.  
  218.  
  219.     for (int i = 0; i < ans.size(); ++i) {
  220.         cout << ans[i].size();
  221.         for (int j = 0; j < ans[i].size(); ++j) {
  222.             cout << "  " << ans[i][j].first << " " << ans[i][j].second;
  223.         }
  224.         cout << "\n";
  225.     }
  226.     return 0;
  227. }
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