BOJ. Passionate Gang-Ho 4 (11378)

On this page

Problem link

Model

There are N workers and M jobs. Each worker has a list of jobs they are qualified to do. A worker may receive one job normally and at most one additional job. Across all workers, the number of additional assignments is at most K. Each job can be assigned to at most one worker. Maximize the total number of assigned jobs.

Maximum-flow construction

Create a source, one vertex per worker, a bonus vertex, one vertex per job, and a sink. Add these edges:

• source → each worker, capacity 1 (the worker’s normal assignment)
• source → bonus vertex, capacity K (the global additional-assignment limit)
• bonus vertex → each worker, capacity 1 (at most one additional assignment for that worker)
• each worker → every eligible job, capacity 1
• each job → sink, capacity 1 (a job is assigned at most once)

A worker can receive at most one unit through each of the two incoming routes, so at most two units total, and at most one of those units can be bonus flow. The bonus vertex can send at most K units in total. Thus a flow yields a valid assignment: each worker has at most two jobs, the total number beyond one per worker is at most the bonus flow and therefore at most K, and each job is used at most once. Conversely, for any valid assignment, route each worker’s first job through the direct source-to-worker edge and, if present, the second through the bonus vertex. This respects all capacities. Integral maximum flow therefore has the same value as the maximum feasible number of assignments.

Algorithm and complexity

Dinic’s algorithm repeatedly builds a level graph with BFS and sends blocking flow along its level-respecting edges. When no source-to-sink path remains in the residual graph, the flow is maximum. Let A be the number of worker-job eligibility edges. This network has V = N + M + 3 vertices and E = A + 2N + M + 1 forward edges. The general time bound for Dinic is O(V^2 E) and its space use is O(V + E). The problem limits are N, M ≤ 1,000 and K ≤ N; no tighter worst-case bound specific to this network is assumed here.

C++17 implementation

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

struct Dinic {
    struct Edge {
        int to;
        int rev;
        int cap;
    };

    vector<vector<Edge>> graph;
    vector<int> level;
    vector<int> nextEdge;

    explicit Dinic(int n)
        : graph(n), level(n), nextEdge(n) {}

    void addEdge(int from, int to, int cap) {
        Edge forward{to, static_cast<int>(graph[to].size()), cap};
        Edge reverse{from, static_cast<int>(graph[from].size()), 0};
        graph[from].push_back(forward);
        graph[to].push_back(reverse);
    }

    bool buildLevels(int source, int sink) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[source] = 0;
        q.push(source);

        while (!q.empty()) {
            int current = q.front();
            q.pop();
            for (const Edge& edge : graph[current]) {
                if (edge.cap > 0 && level[edge.to] == -1) {
                    level[edge.to] = level[current] + 1;
                    q.push(edge.to);
                }
            }
        }
        return level[sink] != -1;
    }

    int sendFlow(int current, int sink, int pushed) {
        if (current == sink || pushed == 0) return pushed;

        for (int& i = nextEdge[current]; i < static_cast<int>(graph[current].size()); ++i) {
            Edge& edge = graph[current][i];
            if (edge.cap == 0 || level[edge.to] != level[current] + 1) continue;

            int sent = sendFlow(edge.to, sink, min(pushed, edge.cap));
            if (sent == 0) continue;

            edge.cap -= sent;
            graph[edge.to][edge.rev].cap += sent;
            return sent;
        }
        return 0;
    }

    int maxFlow(int source, int sink) {
        int total = 0;
        while (buildLevels(source, sink)) {
            fill(nextEdge.begin(), nextEdge.end(), 0);
            while (int sent = sendFlow(source, sink, 1'000'000'000)) {
                total += sent;
            }
        }
        return total;
    }
};

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

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

    const int source = 0;
    const int bonus = n + 1;
    const int firstJob = n + 2;
    const int sink = n + m + 2;
    Dinic dinic(sink + 1);

    for (int worker = 1; worker <= n; ++worker) {
        dinic.addEdge(source, worker, 1);
    }
    dinic.addEdge(source, bonus, k);
    for (int worker = 1; worker <= n; ++worker) {
        dinic.addEdge(bonus, worker, 1);
    }

    for (int worker = 1; worker <= n; ++worker) {
        int count;
        cin >> count;
        while (count--) {
            int job;
            cin >> job;
            dinic.addEdge(worker, firstJob + job - 1, 1);
        }
    }
    for (int job = 0; job < m; ++job) {
        dinic.addEdge(firstJob + job, sink, 1);
    }

    cout << dinic.maxFlow(source, sink) << '\n';
    return 0;
}