Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.26 KB | None | 0 0
  1. #pragma GCC optimize("O3")
  2. #pragma GCC target("avx2")
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <set>
  8. #include <map>
  9. #include <string>
  10. #include <cmath>
  11. #include <queue>
  12. #include <ctime>
  13.  
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17. typedef long double ld;
  18. #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  19. const ll SIZE= 1e5 * 3 + 10, INF = 1e9 * 1e9 + 2, MOD = 1e9 + 7;
  20.  
  21. vector<vector<ll>> graph;
  22. ll q;
  23. vector<ll> vec;
  24. bool used[SIZE];
  25.  
  26. struct edge {
  27. int c, bal, ind, to, fr = -1;
  28. };
  29.  
  30. vector<edge> edges;
  31.  
  32. int n, m, nd;
  33. int dfs(int v, int curMin = INT32_MAX) {
  34. used[v] = true;
  35. if (v == nd) {
  36. return curMin;
  37. }
  38.  
  39. for (auto to : graph[v]) {
  40. if (edges[to].bal > 0 && !used[edges[to].to]) {
  41. int val = dfs(edges[to].to, min(curMin, edges[to].bal));
  42. if (val > 0) {
  43. curMin = min(val, curMin);
  44. edges[to].bal -= curMin;
  45. edges[to ^ 1].bal += curMin;
  46. return curMin;
  47. }
  48. }
  49. }
  50.  
  51. return 0;
  52. }
  53.  
  54. int main() {
  55. cin >> n >> m;
  56.  
  57. nd = n + m + 1;
  58. graph.resize(n + m + 2);
  59. for (int i = 1; i <= n; i++) {
  60. int q;
  61. cin >> q;
  62. while (q != 0) {
  63. q += n;
  64. edges.push_back({ 1, 1, int(edges.size() - 1), q , i});
  65. edges.push_back({ 0, 0, int(edges.size() - 1), i});
  66. graph[i].push_back(edges.size() - 2);
  67. graph[q].push_back(edges.size() - 1);
  68. cin >> q;
  69. }
  70. }
  71.  
  72. for (int i = 1; i <= n; i++) {
  73. edges.push_back({ 1, 1, int(edges.size() - 1), i });
  74. edges.push_back({ 0, 0, int(edges.size() - 1), 0 });
  75. graph[0].push_back(edges.size() - 2);
  76. graph[i].push_back(edges.size() - 1);
  77. }
  78. for (int i = n + 1; i <= n + m; i++) {
  79. edges.push_back({ 1, 1, int(edges.size() - 1), nd });
  80. edges.push_back({ 0, 0, int(edges.size() - 1), i });
  81. graph[i].push_back(edges.size() - 2);
  82. graph[nd].push_back(edges.size() - 1);
  83. }
  84.  
  85. ll q = dfs(0);
  86. while (q != 0) {
  87. for (int i = 0; i <= nd; i++) used[i] = false;
  88. q = dfs(0);
  89. }
  90.  
  91. vector<pair<ll, ll>> ans;
  92. for (int i = 0; i < edges.size(); i++) {
  93. if (edges[i].fr != -1 && edges[i].bal == 0) ans.push_back({ edges[i].fr, edges[i].to - n });
  94. }
  95. cout << ans.size() << "\n";
  96. for (int i = 0; i < ans.size(); i++) {
  97. cout << ans[i].first << " " << ans[i].second << "\n";
  98. }
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement