fork(1) download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int N, P[20], res[20][20], dist[20][20], cnt; vector<int>G[20];
  7. bool used[20], iscenter[20], iscenterpass[20][20];
  8.  
  9. void init() {
  10. for (int i = 0; i < 20; i++) {
  11. for (int j = 0; j < 20; j++) {
  12. res[i][j] = 0; dist[i][j] = 0; iscenterpass[i][j] = false; cnt = 0;
  13. }
  14. G[i].clear(); used[i] = false; iscenter[i] = false;
  15. }
  16. }
  17.  
  18. void dfs(int pos) {
  19. cnt++;
  20. for (int i = 0; i < G[pos].size(); i++) {
  21. if (used[G[pos][i]] == true) continue;
  22. used[G[pos][i]] = true;
  23. dfs(G[pos][i]);
  24. used[G[pos][i]] = false;
  25. }
  26. }
  27.  
  28. void dfs2(int pos, int root, bool flag) {
  29. used[pos] = true; iscenterpass[root][pos] = flag;
  30. for (int i = 0; i < G[pos].size(); i++) {
  31. if (used[G[pos][i]] == true) continue;
  32. bool E = (flag | iscenter[G[pos][i]]);
  33. dfs2(G[pos][i], root, E);
  34. }
  35. }
  36.  
  37. int count_simple_path() {
  38. cnt = 0;
  39. for (int i = 1; i <= N; i++) {
  40. used[i] = true; dfs(i); used[i] = false; cnt--;
  41. }
  42. return cnt / 2;
  43. }
  44.  
  45. void dfs1(int pos, int root, int dep) {
  46. if (dist[root][pos] != (1 << 30)) return;
  47. dist[root][pos] = dep;
  48. for (int i = 0; i < G[pos].size(); i++) dfs1(G[pos][i], root, dep + 1);
  49. }
  50.  
  51. vector<int> get_center() {
  52. for (int i = 1; i <= N; i++) G[i].clear();
  53. for (int i = 2; i <= N; i++) { G[P[i]].push_back(i); G[i].push_back(P[i]); }
  54. for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) dist[i][j] = (1 << 30); }
  55. for (int i = 1; i <= N; i++) dfs1(i, i, 0);
  56.  
  57. int minx = (1 << 30);
  58. for (int i = 1; i <= N; i++) {
  59. int rem = 0;
  60. for (int j = 1; j <= N; j++) rem = max(rem, dist[i][j]);
  61. minx = min(minx, rem);
  62. }
  63.  
  64. vector<int>vec;
  65. for (int i = 1; i <= N; i++) {
  66. int rem = 0;
  67. for (int j = 1; j <= N; j++) rem = max(rem, dist[i][j]);
  68. if (rem == minx) vec.push_back(i);
  69. }
  70. return vec;
  71. }
  72.  
  73. pair<int, int> solve() {
  74. vector<int> centroid = get_center(); for (int i = 0; i < centroid.size(); i++) iscenter[centroid[i]] = true;
  75. for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) used[j] = false; dfs2(i, i, iscenter[i]); }
  76.  
  77. int maxn = 0, maxn2 = 0;
  78. for (int i = 1; i <= N; i++) {
  79. for (int j = i + 1; j <= N; j++) {
  80. for (int k = 0; k <= N; k++) G[k].clear();
  81. for (int k = 2; k <= N; k++) { G[P[k]].push_back(k); G[k].push_back(P[k]); }
  82. G[i].push_back(j); G[j].push_back(i);
  83.  
  84. res[i][j] = count_simple_path();
  85. res[j][i] = res[i][j];
  86. maxn = max(maxn, res[i][j]);
  87. if (iscenterpass[i][j] == true) maxn2 = max(maxn2, res[i][j]);
  88. }
  89. }
  90. return make_pair(maxn, maxn2);
  91. }
  92.  
  93. int cntv = 0, cntw = 0;
  94.  
  95. void dfs_solve(int dep) {
  96. if (dep == N + 1) {
  97. init(); cntw++;
  98. pair<int, int> E = solve();
  99. if (E.first != E.second) {
  100. cntv++;
  101. cout << "Case " << cntv << ":" << endl;
  102. cout << N << endl;
  103. for (int j = 2; j <= N; j++) cout << P[j] << " " << j << endl;
  104. cout << endl;
  105. }
  106. return;
  107. }
  108. for (int j = 1; j < dep; j++) {
  109. P[dep] = j;
  110. dfs_solve(dep + 1);
  111. }
  112. }
  113.  
  114. int main() {
  115. cin >> N;
  116. dfs_solve(2);
  117. cout << cntv << " out of " << cntw << " cases were counter-example" << endl;
  118. return 0;
  119. }
Success #stdin #stdout 0.17s 15248KB
stdin
8
stdout
0 out of 5040 cases were counter-example