fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int maxn = 400 + 10;
  6. int n, g[maxn][maxn];
  7. int id[maxn], love[maxn];
  8. int left[maxn];
  9. bool visy[maxn];
  10. inline bool cmp(int a, int b) {
  11. 	return love[a] > love[b];
  12. }
  13. bool dfs(int u) {
  14. 	for(int i = 1; i <= n; ++i) {
  15. 		if(g[u][i] == 1 && !visy[i]) {
  16. 			visy[i] = true;
  17. 			if(left[i] == -1 || dfs(left[i])) {
  18. 				left[i] = u;
  19. 				return true;
  20. 			}
  21. 		}
  22. 	}
  23. 	return false;
  24. }
  25. int main() {
  26. 	scanf("%d", &n);
  27. 	for(int i = 1; i <= n; ++i) {
  28. 		scanf("%d", &love[i]);
  29. 		id[i] = i;
  30. 	}
  31. 	for(int i = 1, t, u; i <= n; ++i) {
  32. 		scanf("%d", &t);
  33. 		for(int j = 1; j <= t; ++j) {
  34. 			scanf("%d", &u);
  35. 			g[i][u] = 1;
  36. 		}
  37. 	}
  38. 	sort(id + 1, id + n + 1, cmp);
  39. 	memset(left, -1, sizeof left);
  40. 	for(int i = 1; i <= n; ++i) {
  41. 		memset(visy, false, sizeof visy);
  42. 		dfs(id[i]);
  43. 	}
  44. 	memset(love, 0, sizeof love);
  45. 	for(int i = 1; i <= n; ++i) {
  46. 		if(left[i] != -1) {
  47. 			love[left[i]] = i;
  48. 		}
  49. 	}
  50. 	for(int i = 1; i < n; ++i) {
  51. 		printf("%d ", love[i]);
  52. 	}
  53. 	printf("%d\n", love[n]);
  54.  
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 3960KB
comments (?)
stdin
copy 
4 
1 3 2 4 
4 1 2 3 4 
2 1 4 
2 1 4 
2 1 4
stdout
copy 
2 1 0 4
https://ideone.com/gwrZkx
SGU 210. Beloved Sons
language:
C++ (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!