Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<set>
- #include<vector>
- #include<algorithm>
- #include<cmath>
- #include<map>
- #include<string>
- #include<queue>
- #include<fstream>
- #include<iomanip>
- using namespace std;
- int u, mt[100], used[100];
- vector<int> g[100];
- vector<pair<int, int> > pr;
- bool khun(int v)
- {
- if (used[v] == u)
- return false;
- used[v] = u;
- for (int i = 0; i < g[v].size(); i++)
- {
- int to = g[v][i];
- if (mt[to] == -1 || khun(mt[to]))
- {
- mt[to] = v;
- return true;
- }
- }
- return false;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n, k, m, x, y;
- memset(mt, -1, 100);
- cin >> n >> k >> m;
- for (int i = 0; i < m; i++)
- {
- cin >> x >> y;
- x--;
- y--;
- g[x].push_back(y);
- }
- for (int i = 0; i < n; i++)
- {
- u = i + 1;
- khun(i);
- }
- for (int i = 0; i < k; i++)
- if (mt[i] != -1)
- pr.push_back(make_pair(mt[i] + 1, i + 1));
- cout << pr.size() << endl;
- for (int i = 0; i < pr.size(); i++)
- cout << pr[i].first << ' ' << pr[i].second << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement