Hướng dẫn giải của Trại đông Bảo Lộc 2021 - Dây chuyền sản xuất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả: ,
Kiến thức cần biết: Cặp ghép cực đại
- Nhận xét: Nếu tồn tại cách ghép sao cho thời gian tối thiểu là ~X~, thì cũng tồn tại cách ghép sao cho thời gian tối thiểu là ~X - 1~.
Sử dụng kĩ thuật chia nhị phân đáp án, coi các công nhân và công việc là các đỉnh. Tồn tại cạnh nối từ một công nhân ~i~ đến một công việc ~j~ khi và chỉ khi ~c[i][j] \geq X~. Đây chính là đồ thị hai phía, ta chỉ cần dùng thuật toán Hopcroft-Karp để tìm cặp ghép cực đại trên đồ thị hai phía này và kiểm tra xem số cặp ghép có đúng bằng ~n~ hay không.
Độ phức tạp: ~O(n\sqrt{m}.log_2{1e9})~ với ~m~ là số cạnh (~m \approx n^2~).
Code tham khảo:
struct Hopcroft_Karp {
vector<int> G[N];
int dist[N], matchX[N], matchY[N];
int n;
void reset(int _n) {
n = _n;
FOR(i, 1, n) {
G[i].clear();
matchX[i] = matchY[i] = 0;
}
}
bool BFS() {
queue<int> q;
FOR(i, 1, n) if (matchX[i] == 0) {
dist[i] = 0;
q.push(i);
} else dist[i] = -1;
bool betterMatch = false;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int v : G[u]) {
if (matchY[v] == 0)
betterMatch = true;
else if (dist[matchY[v]] == -1) {
dist[matchY[v]] = dist[u] + 1;
q.push(matchY[v]);
}
}
}
return betterMatch;
}
bool DFS(int u) {
for(int v : G[u])
if (matchY[v] == 0 || (dist[matchY[v]] == dist[u] + 1 && DFS(matchY[v]))) {
matchX[u] = v;
matchY[v] = u;
return true;
}
return false;
}
int maxMatching() {
while(BFS()) {
FOR(i, 1, n) if (matchX[i] == 0) DFS(i);
}
int ans = 0;
FOR(i, 1, n) if (matchX[i] > 0)
ans++;
return ans;
}
} MC;
bool check(int X) {
MC.reset(n);
FOR(i, 1, n) FOR(j, 1, n)
if (c[i][j] >= X) (MC.G[i]).pb(j);
return MC.maxMatching() == n;
}
Bình luận