BOJ. Passionate Gang-Ho 2 (11376)

On this page

Problem

Model

There are N workers and M jobs. Each worker lists the jobs they can do. Assign each job to at most one worker, and assign at most two jobs to each worker; maximize the number of assigned jobs.

Make a bipartite graph with two matching slots for each worker. Connect both slots to exactly the jobs that worker can do. A matching uses each slot and each job at most once, so a worker receives at most two jobs and no job is assigned twice. Conversely, any valid assignment can place a worker’s two (or fewer) assigned jobs into their two slots. Thus the maximum matching size is exactly the desired answer.

Augmenting paths

Process every slot with a standard augmenting-path search. For one search, mark jobs rather than slots. When a candidate job is already matched, recursively try to move its current slot to another eligible job. If that succeeds, give the candidate job to the current slot. A job is visited at most once in a search, which prevents cycles; successful reassignment preserves the matching invariant. By the augmenting-path theorem, processing all left-side slots this way produces a maximum matching.

There are 2N slots and E worker-job eligibility edges (counted once per worker). One DFS takes O(E) time, so the total time is O(N E). The graph and matching arrays use O(N + M + E) space.

C++17

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> jobs(n);
    for (int worker = 0; worker < n; ++worker) {
        int count;
        cin >> count;
        jobs[worker].resize(count);
        for (int& job : jobs[worker]) {
            cin >> job;
            --job;
        }
    }

    // matchedSlot[job] is the slot currently assigned to this job.
    vector<int> matchedSlot(m, -1);
    vector<char> visitedJob(m);

    auto augment = [&](auto&& self, int slot) -> bool {
        for (int job : jobs[slot / 2]) {
            if (visitedJob[job]) continue;
            visitedJob[job] = true;

            if (matchedSlot[job] == -1 ||
                self(self, matchedSlot[job])) {
                matchedSlot[job] = slot;
                return true;
            }
        }
        return false;
    };

    int assigned = 0;
    for (int slot = 0; slot < 2 * n; ++slot) {
        fill(visitedJob.begin(), visitedJob.end(), false);
        if (augment(augment, slot)) ++assigned;
    }

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

The recursion only changes ownership along an augmenting path, so each successful search increases the matching by exactly one while keeping every job and slot unique.