fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define rep(_i, _j) for(int _i = 1; _i <= _j; ++_i)
  3. const int INF = 0x3f3f3f3f;
  4. typedef long long LL;
  5. typedef double DB;
  6. using namespace std;
  7.  
  8. const int maxn = 500 + 20;
  9.  
  10. int limit, n, g[maxn][maxn], link[maxn];
  11. bool vis[maxn];
  12. bool dfs(int u) {
  13. 	for(int v = 1; v <= n; ++v) {
  14. 		if(g[u][v] <= limit && !vis[v]) {
  15. 			vis[v] = true;
  16. 			if(link[v] == -1 || dfs(link[v])) {
  17. 				link[v] = u;
  18. 				return true;
  19. 			}
  20. 		}
  21. 	}
  22. 	return false;
  23. }
  24. bool check() {
  25. 	for(int i = 1; i <= n; ++i) {
  26. 		link[i] = -1;
  27. 	}
  28. 	for(int i = 1; i <= n; ++i) {
  29. 		memset(vis, false, sizeof vis);
  30. 		if(!dfs(i)) return false;
  31. 	}
  32. 	return true;
  33. }
  34. int main() {
  35. 	scanf("%d", &n);
  36. 	int low = -1e6, up = 1e6;
  37. 	for(int i = 1; i <= n; ++i) {
  38. 		for(int j = 1; j <= n; ++j) {
  39. 			scanf("%d", &g[i][j]);
  40. 		}
  41. 	}
  42. 	while(low < up) {
  43. 		limit = (low + up) >> 1;
  44. 		if(check()) {
  45. 			up = limit;
  46. 		} else {
  47. 			low = limit + 1;
  48. 		}
  49. 	}
  50. 	printf("%d\n", up);
  51. 	limit = up;
  52. 	check();
  53. 	for(int i = 1; i <= n; ++i) {
  54. 		printf("%d %d\n", link[i], i);
  55. 	}
  56.  
  57. 	return 0;
  58. }
  59.  
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
2 
1 3 
4 5
stdout
copy 
4
2 1
1 2
https://ideone.com/d36to8
SGU 218. Unstable Systems
language:
C++14 (gcc 8.3)
created:
10 years 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!