Hungarain.cpp

// Hungarian Algorithm
// LightOJ 1198

#include <bits/stdc++.h>

using namespace std;

#define MAX 55
#define INF 12345678
int a[MAX][MAX], n, m, x[MAX], y[MAX];

vector<int> hungarain()
{
    vector<int> u (n+1), v (m+1), p (m+1), way (m+1);
    for (int i=1; i<=n; ++i) {
        p[0] = i;
        int j0 = 0;
        vector<int> minv (m+1, INF);
        vector<char> used (m+1, false);
        do {
            used[j0] = true;
            int i0 = p[j0],  delta = INF,  j1;
            for (int j=1; j<=m; ++j)
                if (!used[j]) {
                    int cur = a[i0][j]-u[i0]-v[j];
                    if (cur < minv[j])
                        minv[j] = cur,  way[j] = j0;
                    if (minv[j] < delta)
                        delta = minv[j],  j1 = j;
                }
            for (int j=0; j<=m; ++j)
                if (used[j])
                    u[p[j]] += delta,  v[j] -= delta;
                else
                    minv[j] -= delta;
            j0 = j1;
        } while (p[j0] != 0);
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }
    vector<int> ans (n+1);
    for (int j=1; j<=m; ++j)
        ans[p[j]] = j;
    return ans;
}

int main()
{
    int cases;
    scanf("%d", &cases);
    int caseno = 0;
    while(cases--){
        scanf("%d", &n);
        m = n;
        for(int i=1; i<=n; i++){
            scanf("%d", &x[i]);
        }
        for(int i=1; i<=n; i++){
            scanf("%d", &y[i]);
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(x[i]>y[j]) a[i][j] = -2;
                else if(x[i] == y[j]) a[i][j] = -1;
                else a[i][j] = 0;
            }
        }
        vector<int> ans = hungarain();
        int tot = 0;
        for(int i=1; i<=n; i++){
            int col = ans[i];
            tot += a[i][col]*-1;
        }
        printf("Case %d: %d\n", ++caseno, tot);
    }
}