Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <fstream>
- #include <vector>
- #include <queue>
- #include <functional>
- #include <set>
- #include <map>
- #include <math.h>
- #include <cmath>
- #include <string>
- #include <time.h>
- #include <random>
- #include <unordered_set>
- #include <unordered_map>
- #include <bitset>
- #include <string.h>
- #include <stack>
- using namespace std;
- //
- #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
- #define cin in
- #define cout out
- #define pii pair<int,int>
- #define ll long long
- #define db double
- #define ld long double
- #define uset unordered_set
- #define umap unordered_map
- #define F first
- #define S second
- #define vec vector
- #define ms multiset
- #define pb push_back
- #define pll pair<ll,ll>
- #define pdd pair<ld, ld>
- #define pq priority_queue
- #define umap unordered_map
- #define uset unordered_set
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define pnn pair<Node*, Node*>
- #define uid uniform_int_distribution
- ifstream in("input.txt");
- ofstream out("output.txt");
- const int MAX_N = 200;
- int n, m, k, q_cnt = 0;
- bool g[MAX_N][MAX_N], l_used[MAX_N], r_used[MAX_N], l_spec[MAX_N], r_spec[MAX_N];
- void input() {
- cin >> n >> m >> k;
- int t;
- cin >> t;
- memset(g, 1, sizeof(g));
- while (t--) {
- int a, b;
- cin >> a >> b;
- g[a][b - n] = 0;
- }
- memset(l_used, 0, sizeof(l_used));
- memset(r_used, 0, sizeof(r_used));
- int q;
- cin >> q;
- while (q--) {
- int a;
- cin >> a;
- a--;
- if (a >= n)
- r_spec[a - n] = 1;
- else
- l_spec[a] = 1;
- }
- copy(l_spec, l_spec + MAX_N, l_used);
- copy(r_spec, r_spec + MAX_N, r_used);
- }
- int l_m[MAX_N], r_m[MAX_N];
- bool used[MAX_N];
- bool try_kuhn(int v) {
- if (!l_used[v]) return 0;
- if (used[v]) return 0;
- used[v] = 1;
- for (int to = 0; to < m; to++) {
- if (!r_used[to]) continue;
- if (r_m[to] == -1 || try_kuhn(to)) {
- if (l_spec[v] && l_m[v] == -1)
- q_cnt++;
- if (r_spec[to] && r_m[to] == -1)
- q_cnt++;
- l_m[v] = to;
- r_m[to] = v;
- return 1;
- }
- }
- return 0;
- }
- int main() {
- input();
- //строим макс. парсоч на особенных вершинах
- memset(l_m, 255, sizeof(l_m));
- memset(r_m, 255, sizeof(r_m));
- for (int i = 0; i < n; i++) {
- memset(used, 0, sizeof(used));
- try_kuhn(i);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment