BOJ. Passionate Gang-Ho (11375)

On this page

BOJ 11375: Passionate Gang-Ho

Approach: bipartite matching

Treat each worker as a vertex on the left and each job as a vertex on the right. Draw an edge from a worker to every job they can do. A valid assignment is a matching: no worker and no job can appear in more than one selected edge. The answer is the maximum matching cardinality.

Process workers one at a time and search for an augmenting path with depth-first search. For the current worker, try each eligible job that has not yet been visited in this search. If the job is free, assign it. If it is already assigned, recursively try to move its current worker to another eligible job. When that succeeds, the current worker can take the job. This reassignment is what lets a later search improve an earlier choice instead of leaving a usable job blocked.

The visited array is indexed by jobs and is reset before each starting worker. Mark a job as visited before following its current assignment; this prevents cycles and ensures each job is considered at most once in that search. A successful search increases the matching size by exactly one, while a failed search leaves it unchanged.

The input gives the number of workers N and jobs M, followed by one line per worker: the number of jobs they can do and those job IDs (numbered from 1). Print the maximum number of workers that can be assigned. Each worker and job can be used at most once.

With this DFS implementation, each search takes O(E) time in the worst case, where E is the number of eligibility edges. Running one search for each worker takes O(N E) time; the graph and matching use O(N + M + E) memory.

C++17

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> eligibleJobs;
vector<int> assignedWorker;
vector<bool> visitedJob;

bool findAssignment(int worker) {
    for (int job : eligibleJobs[worker]) {
        if (visitedJob[job]) continue;
        visitedJob[job] = true;

        if (assignedWorker[job] == -1 ||
            findAssignment(assignedWorker[job])) {
            assignedWorker[job] = worker;
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int workerCount, jobCount;
    cin >> workerCount >> jobCount;

    eligibleJobs.resize(workerCount);
    assignedWorker.assign(jobCount, -1);
    for (int worker = 0; worker < workerCount; ++worker) {
        int count;
        cin >> count;
        eligibleJobs[worker].resize(count);
        for (int& job : eligibleJobs[worker]) {
            cin >> job;
            --job;
        }
    }

    int matchingSize = 0;
    for (int worker = 0; worker < workerCount; ++worker) {
        visitedJob.assign(jobCount, false);
        if (findAssignment(worker)) ++matchingSize;
    }

    cout << matchingSize << '\n';
    return 0;
}