Assignment Problem

You are the head of a firm and you have to assign jobs to people. You have N persons working under you and you have N jobs that are to be done by these persons. Each person has to do exactly one job and each job has to be done by exactly one person. Each person has his own capability (in terms of time taken) to do any particular job. Your task is to assign the jobs to the persons in such a way that the total time taken is minimum. A job can be assigned to only one person and a person can do only one job.

• Time : O(n^2)

• Space : O(n^2)

• mcmf의 시간복잡도는 V * E * f이지만 여기서 V = N, E = N, 유량 = 1이라 n^2으로 표현함

class Solution {
    vector<vector<int>> flo, cap, cost;
    vector<int> path;
    vector<vector<int>> adj;
    int source, sink;
    
    bool bfs(int u, int v) {
        path = vector<int>(sink + 1);
        vector<bool> inc(sink + 1);
        vector<int> w(sink + 1, 987654321);
        queue<int> q;
        q.push(u);
        w[u] = 0;
        inc[u] = true;
        
        while(!q.empty()) {
            auto n = q.front(); q.pop();
            inc[n] = false;
            
            for(auto& m : adj[n]) {
                if(cap[n][m] - flo[n][m] > 0 and cost[n][m] + w[n] < w[m]) {
                    w[m] = w[n] + cost[n][m];
                    path[m] = n;
                    if(!inc[m]) {
                        inc[m] = true;
                        q.push(m);
                    }
                }
            }
        }
        
        return path[v] != 0;
    }
    
    int mcmf() {
        int res = 0;
        while(bfs(source, sink)) {
            int v = sink, mi = INT_MAX;
            while(v != source) {
                int u = path[v];
                mi = min(mi, cap[u][v] - flo[u][v]);
                v = u;
            }
            
            v = sink;
            
            while(v != source) {
                int u = path[v];
                
                flo[u][v] += mi;
                flo[v][u] -= mi;
                
                res += cost[u][v];
                
                v = u;
            }
        }
        return res;
    }
public:
    int assignmentProblem(int A[], int n) {
        source = 2 + 2 * n, sink = source + 1;
        cap = cost = flo = vector<vector<int>>(sink + 1, vector<int>(sink + 1));
        adj = vector<vector<int>>(sink + 1);
        path = vector<int>(sink + 1);
        
        int gap = n;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                adj[i + 1].push_back(j + 1 + gap);
                adj[j + 1 + gap].push_back(i + 1);
                
                cap[i + 1][j + 1 + gap] = 1;
                
                cost[i + 1][j + 1 + gap] = A[i*n + j];
                cost[j + 1 + gap][i + 1] = -A[i*n + j];
            }
        }
        
        for(int i = 0; i < n; i++) {
            adj[source].push_back(i + 1);
            adj[i + 1].push_back(source);
            
            cap[source][i+1] = 1;
        }
        
        for(int i = 0; i < n; i++) {
            adj[i + 1 + gap].push_back(sink);
            adj[sink].push_back(i + 1 + gap);
            
            cap[i + 1 + gap][sink] = 1;
        }
        
        return mcmf();
    }
};