fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef complex<double> point;
  7. #define mapii map<int, int>
  8. #define debug(a) cout << #a << ": " << a << endl
  9. #define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
  10. #define fdto(i, r, l) for(int i = (r); i >= (l); --i)
  11. #define fto(i, l, r) for(int i = (l); i <= (r); ++i)
  12. #define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
  13. #define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
  14. #define ii pair<int, int>
  15. #define iii pair<int, ii>
  16. #define ff first
  17. #define ss second
  18. #define mp make_pair
  19. #define pb push_back
  20. #define maxN 105
  21. #define MOD 1000
  22. #define oo 1000000000000000007LL
  23. #define sz(a) (int)a.size()
  24.  
  25. const double PI = acos(-1.0);
  26.  
  27. double fRand(double fMin, double fMax)
  28. {
  29. double f = (double)rand() / RAND_MAX;
  30. return fMin + f * (fMax - fMin);
  31. }
  32.  
  33. template <class T>
  34. T min(T a, T b, T c) {
  35. return min(a, min(b, c));
  36. }
  37.  
  38. template <class T>
  39. T max(T a, T b, T c) {
  40. return max(a, max(b, c));
  41. }
  42.  
  43. int nTest, n, a[maxN][maxN], pU[maxN];
  44. vector<int> g[maxN];
  45. bool visited[maxN];
  46.  
  47. bool DFS(int u) {
  48. if (visited[u]) return false;
  49. visited[u] = true;
  50. for(int v: g[u]) {
  51. if (pU[v] == -1 || DFS(pU[v])) {
  52. pU[v] = u;
  53. return true;
  54. }
  55. }
  56. return false;
  57. }
  58.  
  59. int main () {
  60. scanf("%d", &nTest);
  61. fto(iTest, 1, nTest) {
  62. scanf("%d", &n);
  63. fto(i, 1, n) fto(j, 1, n) scanf("%d", &a[i][j]);
  64.  
  65. int cnt = 0;
  66. fto(x, -n, n) {
  67. fto(u, 1, n) {
  68. g[u].clear();
  69. fto(v, 1, n)
  70. if (a[u][v] == x) g[u].pb(v);
  71. }
  72. fto(v, 1, n) {
  73. visited[v] = false;
  74. pU[v] = -1;
  75. }
  76.  
  77. fto(u, 1, n) {
  78. if (DFS(u)) ++cnt;
  79. }
  80. }
  81.  
  82. int ans = n*n-cnt;
  83. printf("Case #%d: %d\n", iTest, ans);
  84. }
  85.  
  86. return 0;
  87. }
  88.  
Success #stdin #stdout 0s 4300KB
stdin
4
2
1 2
2 1
2
1 1
2 1
2
1 2
1 2
2
2 2
-2 2
stdout
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 1