Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define f first
- #define s second
- using namespace std;
- typedef pair <int, int> pii;
- typedef vector <int> vi;
- typedef vector <pii> vpii;
- const int maxn = 270;
- vi g[maxn];
- int tin[2][maxn], p[2][maxn], n, m, cnt, ap[2][maxn], atin[2][maxn], sz[2], mt[maxn];
- bool used[maxn];
- vpii ans;
- bool try_kuhn (int v) {
- if (used[v]) return false;
- used[v] = true;
- for (int i=0; i < g[v].size(); ++i) {
- int to = g[v][i];
- if (mt[to] == -1 || try_kuhn(mt[to])) {
- mt[to] = v;
- return true;
- }
- }
- return false;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> m;
- sz[0] = n, sz[1] = m;
- for (int i = 0; i < n; ++i) {
- int id = -1;
- while (true) {
- cin >> id;
- if (id == 0) break;
- --id;
- g[i].pb(id);
- }
- }
- for (int i = 0; i < m; ++i) mt[i] = -1;
- cnt = 0;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) used[j] = 0;
- try_kuhn(i);
- }
- for (int i = 0; i < m; ++i)
- if (mt[i] != -1) ans.pb({mt[i] + 1, i + 1});
- cout << ans.size() << endl;
- for (int i = 0; i < ans.size(); ++i) cout << ans[i].f << " " << ans[i].s << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement