3D_Music.cpp 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <memory.h>
  4. #define MAXN 1000
  5. #define MAXM 1000
  6. #define Eps 1e-8
  7. const int dx[4] = {0, 1, 0, -1};
  8. const int dy[4] = {1, 0, -1, 0};
  9. int N, M, P, Q;
  10. int map[MAXN][MAXM];
  11. int size[MAXN*MAXM], pos[MAXN*MAXM], bl[MAXN*MAXM], fa[MAXN * MAXM];
  12. double V[MAXN*MAXM], ans;
  13. int list[MAXN*MAXM][2];
  14. int bfs(int stx, int sty, int ID, int height) {
  15. int head = 0, tail = 1, x, y;
  16. bl[map[stx][sty]] = ID;
  17. list[0][0] = stx; list[0][1] = sty;
  18. while (head < tail) {
  19. size[ID] += height - map[list[head][0]][list[head][1]];
  20. for (int i = 0; i < 4; i ++) {
  21. x = list[head][0] + dx[i];
  22. y = list[head][1] + dy[i];
  23. if (x >= 0 && x < N && y >= 0 && y < M && bl[map[x][y]] == -1 && map[x][y] < height) {
  24. list[tail][0] = x;
  25. list[tail][1] = y;
  26. bl[map[x][y]] = ID;
  27. tail ++;
  28. }
  29. }
  30. head ++;
  31. }
  32. return 0;
  33. }
  34. int pour(int k) {
  35. int cnt = 0, t;
  36. int px = pos[k] / M, py = pos[k] % M;
  37. bool lower[4];
  38. double rest = 0;
  39. memset(lower, 0, sizeof(lower));
  40. for (int i = 0; i < 4; i ++) {
  41. if (px + dx[i] < 0 || px + dx[i] == N || py + dy[i] < 0 || py + dy[i] == M) {
  42. cnt ++;
  43. } else {
  44. t = map[px + dx[i]][py + dy[i]];
  45. if (t < k && (fa[bl[t]] != k || V[bl[t]] < size[bl[t]] - Eps)) {
  46. cnt ++;
  47. lower[i] = true;
  48. }
  49. }
  50. }
  51. for (int i = 0; i < 4; i ++) {
  52. if (px + dx[i] < 0 || px + dx[i] == N || py + dy[i] < 0 || py + dy[i] == M) {
  53. ans += V[bl[k]] / cnt;
  54. } else {
  55. t = map[px + dx[i]][py + dy[i]];
  56. if (lower[i]) {
  57. V[bl[t]] += V[bl[k]] / cnt;
  58. }
  59. if (fa[bl[t]] == k && V[bl[t]] > size[bl[t]]) {
  60. rest += V[bl[t]] - size[bl[t]];
  61. V[bl[t]] = size[bl[t]];
  62. }
  63. }
  64. }
  65. V[bl[k]] = rest;
  66. return 0;
  67. }
  68. bool can(int x, int y) {
  69. if (x == 0 || x == N - 1 || y == 0 || y == M - 1) return true;
  70. for (int i = 0; i < 4; i ++) {
  71. if (bl[map[x + dx[i]][y + dy[i]]] != -1) return true;
  72. }
  73. return false;
  74. }
  75. int main() {
  76. int v1, v2, v3, px, py, x, y;
  77. freopen("fg.in", "r", stdin);
  78. freopen("fg.out", "w", stdout);
  79. scanf("%d%d", &N, &M);
  80. for (int i = 0; i < N; i ++) {
  81. for (int j = 0; j < M; j ++) {
  82. scanf("%d", &map[i][j]);
  83. map[i][j] --;
  84. pos[map[i][j]] = i * M + j;
  85. }
  86. }
  87. memset(bl, 255, sizeof(bl));
  88. memset(fa, 255, sizeof(fa));
  89. for (int i = 0; i < N * M; i ++) {
  90. px = pos[i] / M;
  91. py = pos[i] % M;
  92. if (can(px, py)) {
  93. bl[i] = P ++;
  94. for (int j = 0; j < 4; j ++) {
  95. x = px + dx[j];
  96. y = py + dy[j];
  97. if (x >= 0 && x < N && y >= 0 && y < M && bl[map[x][y]] == -1 && map[x][y] < i) {
  98. fa[P] = i;
  99. bfs(x, y, P ++, i);
  100. }
  101. }
  102. }
  103. }
  104. scanf("%d", &Q);
  105. for (int i = 0; i < Q; i ++) {
  106. scanf("%d%d%d", &v1, &v2, &v3);
  107. v1 --; v2 --;
  108. V[bl[map[v1][v2]]] += v3;
  109. }
  110. for (int i = N * M - 1; i >= 0; i --) if (!size[bl[i]]) {
  111. while (true) {
  112. pour(i);
  113. if (V[bl[i]] < Eps) break;
  114. }
  115. }
  116. printf("%.2lf\n", ans);
  117. return 0;
  118. }