TrickmanOff

Untitled

Dec 7th, 2019
370
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.30 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <fstream>
  4. #include <vector>
  5. #include <queue>
  6. #include <functional>
  7. #include <set>
  8. #include <map>
  9. #include <math.h>
  10. #include <cmath>
  11. #include <string>
  12. #include <time.h>
  13. #include <random>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <bitset>
  17. #include <string.h>
  18. #include <stack>
  19. using namespace std;
  20. //
  21. #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
  22. #define cin in
  23. #define cout out
  24. #define pii pair<int,int>
  25. #define ll long long
  26. #define db double
  27. #define ld long double
  28. #define uset unordered_set
  29. #define umap unordered_map
  30. #define F first
  31. #define S second
  32. #define vec vector
  33. #define ms multiset
  34. #define pb push_back
  35. #define pll pair<ll,ll>
  36. #define pdd pair<ld, ld>
  37. #define pq priority_queue
  38. #define umap unordered_map
  39. #define uset unordered_set
  40. #define pii pair<int, int>
  41. #define pll pair<ll, ll>
  42. #define pnn pair<Node*, Node*>
  43. #define uid uniform_int_distribution
  44.  
  45. ifstream in("input.txt");
  46. ofstream out("output.txt");
  47.  
  48. const int MAX_N = 200;
  49. int n, m, k, q_cnt = 0;
  50. bool g[MAX_N][MAX_N], l_used[MAX_N], r_used[MAX_N], l_spec[MAX_N], r_spec[MAX_N];
  51. void input() {
  52. cin >> n >> m >> k;
  53. int t;
  54. cin >> t;
  55. memset(g, 1, sizeof(g));
  56. while (t--) {
  57. int a, b;
  58. cin >> a >> b;
  59. g[a][b - n] = 0;
  60. }
  61.  
  62. memset(l_used, 0, sizeof(l_used));
  63. memset(r_used, 0, sizeof(r_used));
  64.  
  65. int q;
  66. cin >> q;
  67. while (q--) {
  68. int a;
  69. cin >> a;
  70. a--;
  71. if (a >= n)
  72. r_spec[a - n] = 1;
  73. else
  74. l_spec[a] = 1;
  75. }
  76.  
  77. copy(l_spec, l_spec + MAX_N, l_used);
  78. copy(r_spec, r_spec + MAX_N, r_used);
  79. }
  80.  
  81. int l_m[MAX_N], r_m[MAX_N];
  82.  
  83. bool used[MAX_N];
  84. bool try_kuhn(int v) {
  85. if (!l_used[v]) return 0;
  86.  
  87. if (used[v]) return 0;
  88. used[v] = 1;
  89.  
  90. for (int to = 0; to < m; to++) {
  91. if (!r_used[to]) continue;
  92. if (r_m[to] == -1 || try_kuhn(to)) {
  93. if (l_spec[v] && l_m[v] == -1)
  94. q_cnt++;
  95. if (r_spec[to] && r_m[to] == -1)
  96. q_cnt++;
  97.  
  98. l_m[v] = to;
  99. r_m[to] = v;
  100. return 1;
  101. }
  102. }
  103. return 0;
  104. }
  105.  
  106. int main() {
  107. input();
  108.  
  109. //строим макс. парсоч на особенных вершинах
  110. memset(l_m, 255, sizeof(l_m));
  111. memset(r_m, 255, sizeof(r_m));
  112. for (int i = 0; i < n; i++) {
  113. memset(used, 0, sizeof(used));
  114. try_kuhn(i);
  115. }
  116.  
  117.  
  118. }
Advertisement
Add Comment
Please, Sign In to add comment