fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FNAME "TEST"
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXN = (int)1e3 + 5;
  6. const long long MOD = (long long)29;
  7. #define xd '\n' 
  8. #define fi first
  9. #define se second
  10. const long long base = (long long)256;
  11. const int INF = (int)1e4 + 1;
  12.  
  13. template<class X, class Y> 
  14. 	bool minimize(X &a, Y b) {
  15. 		if(a > b){
  16. 			a = b;
  17. 			return true;
  18. 		}
  19. 		return false;
  20. 	};
  21.  
  22. template<class X, class Y> 
  23. 	bool maximize(X &a, Y b) {
  24. 		if(a < b) {
  25. 			a = b;
  26. 			return true;
  27. 		}
  28. 		return false;
  29. 	};
  30.  
  31. void HuuThien() {
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie(0); cout.tie(0);    
  34.     if (fopen(FNAME".inp", "r")) {
  35.         freopen(FNAME".inp", "r", stdin);
  36.         freopen(FNAME".out", "w", stdout);
  37.     }
  38. }
  39.  
  40. int numX, numY, m;
  41. int matchU[MAXN], matchV[MAXN];
  42. bool visited[MAXN];
  43. vector<int> adj[MAXN];
  44.  
  45. bool dfs(int u) {
  46. 	if(visited[u]) return false;
  47. 	visited[u] = true;
  48.  
  49. 	for(int v : adj[u]) {
  50. 		if((matchV[v] == -1) || dfs(matchV[v])) {
  51. 			matchU[u] = v;
  52. 			matchV[v] = u;
  53. 			return true;
  54. 		}
  55. 	}
  56.  
  57. 	return false;
  58. }
  59.  
  60. void Init() {
  61.     cin >> numX >> numY >> m;
  62.  
  63. 	for(int i = 1; i <= m ; i++) {
  64. 		int u, v;	
  65. 		cin >> u >> v;
  66. 		adj[u].push_back(v);
  67. 	}
  68. }
  69.  
  70. void Solve() {
  71.     memset(matchU, -1, sizeof(matchU));
  72. 	memset(matchV, -1, sizeof(matchV));
  73.  
  74. 	int res = 0;
  75. 	for(int i = 1; i <= numX ; i++) {
  76. 		memset(visited, false, sizeof(visited));
  77. 		if(dfs(i)) {
  78. 			res++;
  79. 		}
  80. 	}
  81.  
  82. 	for(int i = 1; i <= numX ; i++) {
  83. 		if(matchU[i] != -1) {
  84. 			cout << i << " " << matchU[i] << xd;
  85. 		}
  86. 	}
  87.  
  88. 	cout << res;			
  89. }
  90.  
  91. signed main() {
  92. 	HuuThien();
  93.     int test = 1;
  94.     while(test--) {
  95.         Init();
  96.         Solve();
  97.     }
  98.  
  99.     return 0;
  100. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8ykGWy
language:
C++ (gcc 8.3)
created:
2 hours 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!