fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int INF = 0x3f3f3f3f;
  6. const int maxn = 70 + 5;
  7. #define x first
  8. #define y second
  9.  
  10. int n, A[maxn][maxn], B[maxn][maxn];
  11. int g[maxn][maxn], link[maxn], lx[maxn], ly[maxn], slack;
  12. bool visx[maxn], visy[maxn];
  13.  
  14. bool search(int u) {
  15. 	visx[u] = true;
  16. 	for(int v = 1; v <= n; ++v) {
  17. 		if(!visy[v]) {
  18. 			if(lx[u] + ly[v] == g[u][v]) {
  19. 				visy[v] = true;
  20. 				if(link[v] == 0 || search(link[v])) {
  21. 					link[v] = u;
  22. 					return true;
  23. 				}
  24. 			} else {
  25. 				slack = min(slack,lx[u] + ly[v] - g[u][v]);
  26. 			}
  27. 		}
  28. 	}
  29. 	return false;
  30. }
  31.  
  32. pair<int, int> KM() {
  33. 	memset(lx, -INF, sizeof lx);
  34. 	memset(ly, 0, sizeof ly);
  35. 	memset(link, 0, sizeof link);
  36. 	for(int i = 1; i <= n; ++i) {
  37. 		for(int j = 1; j <= n; ++j) {
  38. 			lx[i] = max(lx[i], g[i][j]);
  39. 		}
  40. 	}
  41. 	for(int i = 1; i <= n; ++i) {
  42. 		for( ; ; ) {
  43. 			slack = INF;
  44. 			memset(visx, false, sizeof visx);
  45. 			memset(visy, false, sizeof visy);
  46. 			if(search(i)) {
  47. 				break;
  48. 			} else {
  49. 				for(int j = 1; j <= n; ++j) {
  50. 					if(visx[j]) {
  51. 						lx[j] -= slack;
  52. 					}
  53. 					if(visy[j]) {
  54. 						ly[j] += slack;
  55. 					}
  56. 				}
  57. 			}
  58. 		}
  59. 	}
  60. 	int x = 0, y = 0;
  61. 	for(int i = 1; i <= n; ++i) {
  62. 		x += A[link[i]][i];
  63. 		y += B[link[i]][i];
  64. 	}
  65. 	return make_pair(x, y);
  66. }
  67.  
  68. int work(pair<int, int> s, pair<int, int> t) {
  69. 	// 两点式 (y - y2) / (y1 - y2) = (x - x2) / (x1 - x2)
  70. 	int a = s.x - t.x, b = t.y - s.y;
  71. 	for(int i = 1; i <= n; ++i) {
  72. 		for(int j = 1; j <= n; ++j) {
  73. 			g[i][j] = b * A[i][j] + a * B[i][j];
  74. 		}
  75. 	}
  76. 	pair<int, int> ret = KM();
  77. 	if(ret == s || ret == t) {
  78. 		return min(t.x * t.y, s.x * s.y);
  79. 	}
  80. 	return min(work(s, ret), work(ret, t));
  81. }
  82.  
  83. int solve() {
  84. 	for(int i = 1; i <= n; ++i) {
  85. 		for(int j = 1; j <= n; ++j) {
  86. 			g[i][j] = -A[i][j];
  87. 		}
  88. 	}
  89. 	pair<int, int> s = KM();
  90. 	for(int i = 1; i <= n; ++i) {
  91. 		for(int j = 1; j <= n; ++j) {
  92. 			g[i][j] = -B[i][j];
  93. 		}
  94. 	}
  95. 	pair<int, int> t = KM();
  96. 	return work(s, t);
  97. }
  98.  
  99. int main() {
  100. 	int T;
  101. 	scanf("%d", &T);
  102. 	while(T--) {
  103. 		scanf("%d", &n);
  104. 		for(int i = 1; i <= n; ++i) {
  105. 			for(int j = 1; j <= n; ++j) {
  106. 				scanf("%d", &A[i][j]);
  107. 			}
  108. 		}
  109. 		for(int i = 1; i <= n; ++i) {
  110. 			for(int j = 1; j <= n; ++j) {
  111. 				scanf("%d", &B[i][j]);
  112. 			}
  113. 		}
  114. 		printf("%d\n", solve());
  115.  
  116. 	}
  117.  
  118. 	return 0;
  119. }
Success #stdin #stdout 0s 3408KB
comments (?)
stdin
copy 
1
3
4 3 2
2 3 4
3 2 1

2 3 2
2 2 4
1 1 3
stdout
copy 
30
https://ideone.com/gIQUGU
HNOI2014 画框 frame
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!