fork download
copy 
  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
comments (?)
stdin
copy 
4
2
1 2
2 1
2
1 1
2 1
2
1 2
1 2
2
2 2
-2 2
stdout
copy 
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 1
https://ideone.com/lVaRDO
language:
C++14 (clang 8.0)
created:
5 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!