백준 1258번: 문제 할당 [C++]

작성일 | In
플래티넘 III 플래티넘 III

문제

문제 할당

풀이

학생과 문제를 그래프로 모델링해서 최소 비용 최대 유량 알고리즘으로 해결할 수 있습니다.

유량을 해결한 문제 수, 비용을 문제를 푸는 시간으로 생각합시다.

학생과 문제를 용량을 1, 비용을 문제를 푸는 데 걸리는 시간으로 하는 간선으로 이어줍니다.

각 학생들은 최대 한 문제만 풀 수 있으므로 소스에서 학생으로 용량이 1, 비용이 0인 간선으로 이어줍니다.

각 문제는 최대 한 번만 해결될 수 있으므로 문제에서 싱크로 용량이 1, 비용이 0인 간선으로 이어줍니다.

코드

zkw MCMF로 작성했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

constexpr int INF = 1e9;

struct FlowNetwork {
    struct Edge {
        int to, capacity, flow, cost, rev;
    };

    int n, source, sink;
    vector<vector<Edge>> adj;
    vector<int> curEdge, h;
    vector<bool> visited;

    FlowNetwork(int n, int source, int sink)
        : n(n),
          source(source),
          sink(sink),
          adj(n),
          curEdge(n),
          h(n),
          visited(n) {}

    void addEdge(int from, int to, int capacity, int cost) {
        adj[from].emplace_back(to, capacity, 0, cost, adj[to].size());
        adj[to].emplace_back(from, 0, 0, -cost, adj[from].size() - 1);
    }

    int pushFlow(int cur, int flow) {
        visited[cur] = true;

        if (cur == sink)
            return flow;

        for (int& i = curEdge[cur]; i < adj[cur].size(); i++) {
            Edge& edge = adj[cur][i];

            if (visited[edge.to] or edge.capacity - edge.flow == 0 or
                h[cur] + edge.cost - h[edge.to] != 0)
                continue;

            int bottleneck =
                pushFlow(edge.to, min(flow, edge.capacity - edge.flow));

            if (bottleneck == 0)
                continue;

            edge.flow += bottleneck;
            adj[edge.to][edge.rev].flow -= bottleneck;

            return bottleneck;
        }

        return 0;
    }

    bool updateDAG() {
        int delta = INF;

        for (int i = 0; i < n; i++) {
            if (not visited[i])
                continue;

            for (auto& [to, capacity, flow, cost, _] : adj[i]) {
                if (capacity - flow != 0 and not visited[to])
                    delta = min(delta, h[i] + cost - h[to]);
            }
        }

        if (delta == INF)
            return false;

        for (int i = 0; i < n; i++) {
            if (not visited[i])
                h[i] += delta;
        }

        return true;
    }

    int getMinCostOfMaxFlow() {
        int mc = 0;

        ranges::fill(h, INF);
        queue<int> q;
        vector<bool> inQueue(n);

        h[source] = 0;
        q.push(source);

        while (not q.empty()) {
            int cur = q.front();
            q.pop();
            inQueue[cur] = false;

            for (auto& [to, capacity, flow, cost, _] : adj[cur]) {
                if (capacity - flow == 0 or h[to] <= h[cur] + cost)
                    continue;

                h[to] = h[cur] + cost;

                if (inQueue[to])
                    continue;

                q.push(to);
                inQueue[to] = true;
            }
        }

        do {
            ranges::fill(curEdge, 0);
            ranges::fill(visited, false);

            while (true) {
                int bottleneck = pushFlow(source, INF);
                if (bottleneck == 0)
                    break;
                mc += bottleneck * h[sink];

                ranges::fill(visited, false);
            }

        } while (updateDAG());

        return mc;
    }
};

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

    int N;
    cin >> N;

    int source = 0, sink = N * 2 + 1;
    FlowNetwork flowNetwork(N * 2 + 2, source, sink);

    for (int i = 1; i <= N; i++) {
        flowNetwork.addEdge(source, i, 1, 0);
        flowNetwork.addEdge(N + i, sink, 1, 0);

        for (int j = N + 1; j <= 2 * N; j++) {
            int t;
            cin >> t;

            flowNetwork.addEdge(i, j, 1, t);
        }
    }

    cout << flowNetwork.getMinCostOfMaxFlow();

    return 0;
}

백준 1258번: 문제 할당 [C++]