fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1005;
  5. const int INF = 1e9;
  6.  
  7. int n, m, k;
  8. vector<int> adj[N];
  9.  
  10. int rightMatch[N], leftMatch[N];
  11. int dist[N];
  12. bool vis[N], flag[2*N];
  13.  
  14. // assume that leftSide is numbered [1..n], rightSide [1..m]
  15. // leftMatch[i] -> i-th left matched with who on the rightSide
  16. // rightMatch[i] -> opposite
  17. void bfs() {
  18.   queue<int> q;
  19.   for (int i = 1; i <= n; i++)
  20.     if (leftMatch[i] == -1) {
  21.       dist[i] = 0;
  22.       q.push(i);
  23.     } else
  24.       dist[i] = INF;
  25.  
  26.   while (!q.empty()) {
  27.     int cur = q.front();
  28.     q.pop();
  29.  
  30.     for (int nex : adj[cur]) {
  31.       if (rightMatch[nex] != -1 && dist[rightMatch[nex]] == INF) {
  32.         dist[rightMatch[nex]] = dist[cur] + 1;
  33.         q.push(rightMatch[nex]);
  34.       }
  35.     }
  36.   }
  37. }
  38.  
  39. int augment(int now) {
  40.   if (vis[now]) return 0;
  41.   vis[now] = 1;
  42.  
  43.   for (int nex : adj[now]) {
  44.     if (rightMatch[nex] == -1 ||
  45.         (dist[rightMatch[nex]] == dist[now] + 1 && augment(rightMatch[nex]))) {
  46.       rightMatch[nex] = now;
  47.       leftMatch[now] = nex;
  48.       return 1;
  49.     }
  50.   }
  51.  
  52.   return 0;
  53. }
  54.  
  55. int hopcroftKarp() {
  56.   int ret = 0;
  57.   memset(leftMatch, -1, sizeof leftMatch);
  58.   memset(rightMatch, -1, sizeof rightMatch);
  59.  
  60.   while (1) {
  61.     bfs();
  62.     memset(vis, 0, sizeof vis);
  63.  
  64.     int add = 0;
  65.     for (int i = 1; i <= n; i++)
  66.       if (leftMatch[i] == -1) {
  67.         add += augment(i);
  68.       }
  69.  
  70.     if (add == 0) {
  71.       break;
  72.     }
  73.     ret += add;
  74.   }
  75.  
  76.   return ret;
  77. }
  78.  
  79. void dfsMark(int now) {
  80.   if (now == -1 || flag[now]) return;
  81.   flag[now] = true;
  82.  
  83.   for (int nex : adj[now]) {
  84.     if (rightMatch[nex] != now) {
  85.       flag[n+nex] = 1;
  86.       dfsMark(rightMatch[nex]);
  87.     }
  88.   }
  89. }
  90.  
  91. vector<int> konigs() {
  92.   memset(flag, 0, sizeof flag);
  93.   for (int i = 1; i <= n; i++)
  94.     if (leftMatch[i] == -1) {
  95.       dfsMark(i);
  96.     }
  97.  
  98.   // for (int i = 1 ; i <= n ; i++) {
  99.   //   printf("left %d -> match %d %d\n", i, leftMatch[i], flag[i]);
  100.   // }
  101.  
  102.   // for (int i = 1 ; i <= m ; i++) {
  103.   //   printf("right %d -> match %d %d\n", i, rightMatch[i], flag[i]);
  104.   // }
  105.  
  106.   vector<int> mvc, mis;
  107.   // leftSide
  108.   for (int i = 1; i <= n; i++) {
  109.     if (!flag[i])
  110.       mvc.push_back(i);
  111.     else
  112.       mis.push_back(i);
  113.   }
  114.   // rightSide
  115.   for (int i = 1; i <= m; i++) {
  116.     if (flag[n+i])
  117.       mvc.push_back(n+i);
  118.     else
  119.       mis.push_back(n+i);
  120.   }
  121.  
  122.   // now do whatever you want with mvc or mis
  123.   return mvc;
  124. }
  125.  
  126. bool init() {
  127.   if (scanf("%d %d %d", &n, &m, &k) != 3) {
  128.     return false;
  129.   }
  130.  
  131.   if (n == 0 && m == 0 && k == 0) {
  132.     return false;
  133.   }
  134.  
  135.   for (int i = 1 ; i <= n ; i++) adj[i].clear();
  136.   for (int i = 1 ; i <= k ; i++) {
  137.     int r, c;
  138.     scanf("%d %d", &r, &c);
  139.  
  140.     adj[r].push_back(c);
  141.   }
  142.  
  143.   return true;
  144. }
  145.  
  146. void work() {
  147.   int ret = hopcroftKarp();
  148.   printf("%d", ret);
  149.  
  150.   vector<int> mvc = konigs();
  151.   for (int x : mvc) {
  152.     if (x > n) printf(" c%d", x-n);
  153.     else printf(" r%d", x);
  154.   }
  155.   puts("");
  156. }
  157.  
  158. int main() {
  159.   while (init()) {
  160.     work();
  161.   }
  162.   return 0;
  163. }
Success #stdin #stdout 0s 15280KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/h64DsS
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!