fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. const int N = 2e5 + 5;
  7. int n, m, k;
  8. int L[N], R[N], vis[N], vers = 0;
  9. vector<int> D[N], G[N];
  10.  
  11. bool dfs(int u) {
  12.     vis[u] = vers;
  13.     for (int v: D[u]) if (!L[v]) {
  14.         L[v] = u;
  15.         R[u] = v;
  16.         return 1;
  17.     }
  18.     for (int v: D[u]) if (vis[L[v]] != vers && dfs(L[v])) {
  19.         L[v] = u;
  20.         R[u] = v;
  21.         return 1;
  22.     }
  23.     return 0;
  24. }
  25.  
  26. void maximumMatching() {
  27.     while(1) {
  28.         vers++;
  29.         bool ok = 0;
  30.         for (int u = 1; u <= n; u++) if (!R[u] && dfs(u)) ok = 1;
  31.         if (!ok) break;
  32.     }
  33. }
  34.  
  35. void cover(int u) {
  36.     vis[u] = 1;
  37.     for (int v: G[u]) if (!vis[v]) cover(v);
  38. }
  39.  
  40. void minimumVertexCover() {
  41.     fill(vis + 1, vis + n + m + 1, 0);
  42.     for (int u = 1; u <= n; u++) {
  43.         for (int v: D[u]) {
  44.             if (v != R[u]) G[u].push_back(v);
  45.             else G[v].push_back(u);
  46.         }
  47.     }
  48.     for (int u = 1; u <= n; u++) if (!R[u] && !vis[u]) cover(u);
  49. }
  50.  
  51. signed main() {
  52.     cin.tie(NULL)->sync_with_stdio(false);
  53.     if(ifstream("FOODS.inp")) {
  54.         freopen("FOODS.inp", "r", stdin);
  55.         freopen("FOODS.out", "w", stdout);
  56.     }
  57.     cin >> n >> m >> k;
  58.     for (int i = 1; i <= k; i++) {
  59.         int u, v; cin >> u >> v;
  60.         v += n;
  61.         D[u].push_back(v);
  62.     }
  63.     maximumMatching();
  64.     minimumVertexCover();
  65.     vector<int> P, Q;
  66.     for (int u = 1; u <= n; u++) if (!(R[u] && !vis[u])) P.push_back(u);
  67.     for (int v = n + 1; v <= n + m; v++) if (!(L[v] && vis[v])) Q.push_back(v - n);
  68.     cout << P.size() << " " << Q.size() << '\n';
  69.     for (int item: P) cout << item << " ";
  70.     for (int item: Q) cout << item << " ";
  71.     return 0;
  72. }
  73.  
  74.  
  75. /*
  76. cho đồ thị 2 phía n (trái), m (phải), k(cạnh)
  77. cần tìm max n0 + m0 đỉnh sao cho không có đỉnh nào trong tập n0 có cạnh nối tới đỉnh bất kì trong m0:
  78. Có thể đây chính là bài Maximum independent set in Bipartite graph
  79. Maximum independent set in Bipartite graph = |Node| - Maximum Matching
  80. (chx chứng minh được):
  81. Và trace sẽ là những đỉnh còn lại chưa được đánh dấu trong bài Minimum vertex cover in bipartite graph
  82.  
  83. Nhắc lại bài Minimum vertex cover in bipartie graph:
  84.  
  85. *Minimum vertex cover in bipartite graph.
  86. ->Để tìm số đỉnh tối thiểu để bao phủ hết các cạnh trong đồ thị 2 phía, ta chỉ cần tìm cặp ghép cực đại
  87. Vì:
  88. + Kőnig's theorem (graph theory) cho rằng: trong đồ thị vô hướng số lượng đỉnh trong tập hợp
  89. độc lập lớn nhất >= cặp ghép cực đại. Từ đó suy ra Cặp ghép cực đại = số đỉnh cực tiểu bao phủ
  90. # Chứng minh: https://c...content-available-to-author-only...s.com/blog/entry/105697
  91. # Video: https://w...content-available-to-author-only...e.com/watch?v=K-g5AzHACWs
  92. + Để trace, tìm lại các đỉnh đó, ta làm như sau
  93. - Giả sử đã tìm được M cạnh của cặp ghép cực đại.
  94. - Hãy định nghĩa hướng của các cạnh. Những cạnh thuộc tập M sẽ đi từ phải sang trái, còn lại đi từ trái sang phải
  95. - Bây giờ, hãy Dfs từ TẤT CẢ các đỉnh BÊN TRÁI KHÔNG thuộc tập M
  96. - Một số đỉnh của đồ thị sẽ được đánh dấu là đã thăm trong quá trình DFS này và một số không được thăm.
  97. - Để có được bộ che đỉnh tối thiểu, bạn lấy tất cả các đỉnh bên phải ĐÃ được thăm của M, và tất cả các đỉnh bên trái CHƯA được thăm của M. 
  98. # Chứng minh bằng phản chứng: 
  99.   Lấy một cạnh (l, r) mà giả sử không được bao phủ
  100.   và xem xét cả bốn trường hợp liên quan đến l và r có liên quan đến các cạnh trong M hay không.
  101.   Trong tất cả những trường hợp này sẽ có một mâu thuẫn với cách mà chúng ta đã thực hiện DFS
  102.   và thực tế rằng M là một sự khớp tối đa.
  103. # Nguồn: https://c...content-available-to-author-only...s.com/blog/entry/17534
  104. Ví dụ: Bài LIGHTING (CHIẾU SÁNG)
  105.  
  106. */
Success #stdin #stdout 0.01s 13468KB
comments (?)
stdin 
Standard input is empty
stdout 
0 0
https://ideone.com/eSKFXE
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

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!