Guest User

B with Dinic

a guest
Apr 4th, 2021
212
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5.  
  6. // Dinic's algorithm for max flow
  7. // O(V^2 E) in general
  8. // O(min(V^{2/3}, E^1/2) E) in graphs with unit capacities
  9. // O(sqrt{V} E) in unit networks (e.g. bipartite matching)
  10. class Dinic {
  11. private:
  12. const static ll INF = 8*(ll)1e18;
  13. struct Edge {
  14. const int t; // Endpoint
  15. ll a; // Admissible flow
  16. Edge(int tar, ll cap = INF) : t(tar), a(cap) {}
  17. };
  18.  
  19. vector<Edge> edges;
  20. vector<vector<int>> conns;
  21. vector<int> dist, act_ind;
  22.  
  23. ll push(int ei, ll v) {
  24. edges[ei].a -= v;
  25. edges[ei ^ 1].a += v;
  26. return v;
  27. }
  28. void calcDists(int sink) {
  29. for (int& v : dist) v = -1;
  30. dist[sink] = 0;
  31. vector<int> que = {sink};
  32. for (int j = 0; j < que.size(); ++j) {
  33. for (auto ei : conns[que[j]]) {
  34. int t = edges[ei].t;
  35. if (edges[ei^1].a > 0 && dist[t] == -1) {
  36. dist[t] = dist[que[j]] + 1;
  37. que.push_back(t);
  38. }
  39. }
  40. }
  41. }
  42. ll dfsFlow(int i, int sink, ll cap) {
  43. if (i == sink) return 0;
  44. for (int& j = act_ind[i]; j < conns[i].size(); ++j) {
  45. int ei = conns[i][j];
  46. int t = edges[ei].t;
  47. if (dist[t] != dist[i] - 1 || edges[ei].a == 0) continue;
  48.  
  49. ll subcap = min(cap, edges[ei].a);
  50. cap -= push(ei, subcap - dfsFlow(t, sink, subcap));
  51. if (! cap) return 0;
  52. }
  53. return cap;
  54. }
  55. public:
  56. Dinic(int n) : conns(n), dist(n), act_ind(n) {}
  57.  
  58. int addEdge(int s, int t, ll c = INF, bool dir = 1) {
  59. int i = edges.size() / 2;
  60. edges.emplace_back(t, c);
  61. edges.emplace_back(s, dir ? 0 : c);
  62. conns[s].push_back(2*i);
  63. conns[t].push_back(2*i+1);
  64. return i;
  65. }
  66. ll pushFlow(int source, int sink) {
  67. for (ll res = 0;;) {
  68. calcDists(sink);
  69. if (dist[source] == -1) return res;
  70. for (int& v : act_ind) v = 0;
  71. res += INF - dfsFlow(source, sink, INF);
  72. }
  73. }
  74. // Returns a min-cut containing the sink
  75. vector<int> minCut() {
  76. vector<int> res;
  77. for (int i = 0; i < dist.size(); ++i) {
  78. if (dist[i] == -1) res.push_back(i);
  79. }
  80. return res;
  81. }
  82. // Gives flow on edge assuming it is directed/undirected. Undirected flow is signed.
  83. ll getDirFlow(int i) const { return edges[2*i+1].a; }
  84. ll getUndirFlow(int i) const { return (edges[2*i+1].a - edges[2*i].a) / 2; }
  85. };
  86.  
  87. int main() {
  88. ios_base::sync_with_stdio(false);
  89. cin.tie(0);
  90.  
  91. int d, n;
  92. cin >> d >> n;
  93.  
  94. vector<int> nodes(n);
  95. vector<vector<int>> layers(d);
  96. for (int i = 0; i < n; ++i) {
  97. string str;
  98. cin >> str;
  99. int ind = 0;
  100. for (int j = 0; j < d; ++j) {
  101. if (str[j] == '1') ind += 1 << j;
  102. }
  103. nodes[i] = ind;
  104. layers[__builtin_popcount(ind) - 1].push_back(i);
  105. }
  106.  
  107. Dinic dinic(2*n + 2);
  108. int so = 2*n;
  109. int si = 2*n+1;
  110.  
  111. vector<pair<int, pair<int, int>>> edges;
  112. for (int i = 0; i < n; ++i) {
  113. dinic.addEdge(so, i, 1);
  114. dinic.addEdge(i+n, si, 1);
  115. }
  116. for (int j = d-2; j >= 0; --j) {
  117. for (int i = j+1; i < d; ++i) {
  118. for (int y : layers[j]) {
  119. for (int x : layers[i]) {
  120. if ((nodes[x] & nodes[y]) == nodes[y]) {
  121. int ind = dinic.addEdge(y, x+n, 1);
  122. edges.emplace_back(ind, make_pair(y, x));
  123. }
  124. }
  125. }
  126. }
  127. dinic.pushFlow(so, si);
  128. }
  129.  
  130. vector<int> nxt(n, -1), pre(n, -1);
  131. for (auto pr : edges) {
  132. if (dinic.getDirFlow(pr.first)) {
  133. int y = pr.second.first;
  134. int x = pr.second.second;
  135. nxt[y] = x;
  136. pre[x] = y;
  137. }
  138. }
  139.  
  140. vector<int> starts;
  141. for (int i = 0; i < n; ++i) {
  142. if (pre[i] == -1) starts.push_back(i);
  143. }
  144.  
  145. vector<int> res;
  146. while(! starts.empty()) {
  147. int cur = 0;
  148. int ind = starts.back();
  149. starts.pop_back();
  150.  
  151. while(ind != -1) {
  152. for (int j = 0; j < d; ++j) {
  153. if (cur & (1 << j)) continue;
  154. if (! (nodes[ind] & (1 << j))) continue;
  155. res.emplace_back(j);
  156. }
  157. cur = nodes[ind];
  158. ind = nxt[ind];
  159. }
  160. res.push_back(-1);
  161. }
  162. res.pop_back();
  163.  
  164. cout << res.size() << '\n';
  165. for (auto v : res) {
  166. if (v == -1) cout << "R ";
  167. else cout << v << ' ';
  168. }
  169. cout << '\n';
  170. }
  171.  
RAW Paste Data