Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define f first
  5. #define s second
  6.  
  7. using namespace std;
  8.  
  9. typedef pair <int, int> pii;
  10. typedef vector <int> vi;
  11. typedef vector <pii> vpii;
  12.  
  13. const int maxn = 270;
  14.  
  15. vi g[maxn];
  16. int tin[2][maxn], p[2][maxn], n, m, cnt, ap[2][maxn], atin[2][maxn], sz[2], mt[maxn];
  17. bool used[maxn];
  18. vpii ans;
  19.  
  20. bool try_kuhn (int v) {
  21.     if (used[v]) return false;
  22.     used[v] = true;
  23.     for (int i=0; i < g[v].size(); ++i) {
  24.         int to = g[v][i];
  25.         if (mt[to] == -1 || try_kuhn(mt[to])) {
  26.             mt[to] = v;
  27.             return true;
  28.         }
  29.     }
  30.     return false;
  31. }
  32.  
  33. int main() {
  34.  
  35.     ios_base::sync_with_stdio(0);
  36.     cin.tie(0);
  37.     cout.tie(0);
  38.  
  39.     cin >> n >> m;
  40.     sz[0] = n, sz[1] = m;
  41.     for (int i = 0; i < n; ++i) {
  42.         int id = -1;
  43.         while (true) {
  44.             cin >> id;
  45.             if (id == 0) break;
  46.             --id;
  47.             g[i].pb(id);
  48.         }
  49.     }
  50.  
  51.     for (int i = 0; i < m; ++i) mt[i] = -1;
  52.     cnt = 0;
  53.     for (int i = 0; i < n; ++i) {
  54.         for (int j = 0; j < n; ++j) used[j] = 0;
  55.         try_kuhn(i);
  56.     }
  57.  
  58.     for (int i = 0; i < m; ++i)
  59.         if (mt[i] != -1) ans.pb({mt[i] + 1, i + 1});
  60.     cout << ans.size() << endl;
  61.     for (int i = 0; i < ans.size(); ++i) cout << ans[i].f << " " << ans[i].s << endl;
  62.  
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement