Hướng dẫn giải của [200 đề thầy Đức] Bài 177: Đội cờ
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 viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Mỗi trận có điểm: đội B được 2 điểm nếu thắng (trình độ $b > a$), 1 điểm nếu hòa ($b = a$), 0 điểm nếu thua. Đội B được chọn cách ghép giữa $n$ cầu thủ của A và $n$ cầu thủ của B, tức là một hoán vị. Cần tìm hoán vị cho tổng điểm lớn nhất. Đây là bài ghép cặp hai phía có trọng số, dùng thuật toán ghép cặp tối ưu.
Sub 1: Thuật toán Hungarian — ~O(n^3)~, dùng khi ~n \le 200~
Ghép cặp tối ưu trên ma trận chi phí $c = -\text{điểm}$. Thuật toán Hungarian tìm phép ghép có tổng chi phí nhỏ nhất trong $O(n^3)$, từ đó có tổng điểm lớn nhất.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Luồng chi phí nhỏ nhất trên giá trị nén — ~O(V^2 \cdot \text{số lần tăng luồng})~
Trình độ chỉ từ 1 đến 100, nên gom các cầu thủ cùng trình độ thành một nhóm có số lượng. Dựng mạng: nguồn $\to$ nhóm A (sức chứa là số cầu thủ), nhóm A $\to$ nhóm B với chi phí $2 - \text{điểm}$ (luôn không âm), nhóm B $\to$ đích. Chạy luồng cực đại chi phí nhỏ nhất với Dijkstra có thế năng, lượng luồng là $n$. Tổng điểm $= 2n - \text{chi phí}$.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc $n$ và các cặp trình độ. Nếu $n \le 200$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a, b; // a[i], b[i]: trinh do cau thu thu i cua doi A va doi B
// Diem doi B gap doi A khi B co trinh do y, A co trinh do x: 2 thang, 1 hoa, 0 thua
int score(int x, int y) {
if (y > x) return 2;
if (y == x) return 1;
return 0;
}
// Sub 1: Hungarian (ghep cap toi uu) O(n^3), dung khi n <= 200.
// Dung chi phi c = -diem de tim cap ghep co tong diem lon nhat.
void sub1() {
const int INF = 1e9;
vector<int> u(n + 1, 0), v(n + 1, 0), p(n + 1, 0), way(n + 1, 0);
for (int i = 1; i <= n; i++) {
p[0] = i;
int j0 = 0;
vector<int> minv(n + 1, INF);
vector<char> used(n + 1, false);
do {
used[j0] = true;
int i0 = p[j0], delta = INF, j1 = 0;
for (int j = 1; j <= n; j++)
if (!used[j]) {
int cur = -score(a[i0 - 1], b[j - 1]) - u[i0] - v[j];
if (cur < minv[j]) {
minv[j] = cur;
way[j] = j0;
}
if (minv[j] < delta) {
delta = minv[j];
j1 = j;
}
}
for (int j = 0; j <= n; j++)
if (used[j]) {
u[p[j]] += delta;
v[j] -= delta;
} else {
minv[j] -= delta;
}
j0 = j1;
} while (p[j0] != 0);
do {
int j1 = way[j0];
p[j0] = p[j1];
j0 = j1;
} while (j0);
}
long long total = 0;
for (int j = 1; j <= n; j++) total += score(a[p[j] - 1], b[j - 1]);
cout << total << "\n";
}
// Sub 2: dem theo gia tri. Trinh do <= 100 nen gom cac cau thu cung trinh do thanh mot nhom,
// roi tim luong ghep toi uu (min-cost max-flow) giua 100 nhom A va 100 nhom B.
// Chi phi moi cap = 2 - diem (khong am), nen Dijkstra voi the dung duoc.
struct Edge {
int to, rev;
long long cap, cost;
};
vector<vector<Edge>> G;
void addEdge(int u, int v, long long cap, long long cost) {
G[u].push_back({v, (int)G[v].size(), cap, cost});
G[v].push_back({u, (int)G[u].size() - 1, 0, -cost});
}
long long minCostFlow(int s, int t, long long maxf) {
int V = G.size();
const long long INF = LLONG_MAX / 4;
vector<long long> h(V, 0), dist(V);
vector<int> pv(V), pe(V);
long long flow = 0, cost = 0;
while (flow < maxf) {
fill(dist.begin(), dist.end(), INF);
vector<char> done(V, false);
dist[s] = 0;
for (int it = 0; it < V; it++) { // Dijkstra O(V^2)
int u = -1;
for (int x = 0; x < V; x++)
if (!done[x] && dist[x] < INF && (u == -1 || dist[x] < dist[u])) u = x;
if (u == -1) break;
done[u] = true;
for (int k = 0; k < (int)G[u].size(); k++) {
Edge &e = G[u][k];
if (e.cap > 0) {
long long nd = dist[u] + e.cost + h[u] - h[e.to];
if (nd < dist[e.to]) {
dist[e.to] = nd;
pv[e.to] = u;
pe[e.to] = k;
}
}
}
}
if (dist[t] == INF) break;
for (int x = 0; x < V; x++)
if (dist[x] < INF) h[x] += dist[x];
long long d = maxf - flow;
for (int x = t; x != s; x = pv[x]) d = min(d, G[pv[x]][pe[x]].cap);
flow += d;
cost += d * (h[t] - h[s]);
for (int x = t; x != s; x = pv[x]) {
Edge &e = G[pv[x]][pe[x]];
e.cap -= d;
G[x][e.rev].cap += d;
}
}
return cost;
}
void sub2() {
// Nut: S = 0, nhom A gia tri x (1..100) -> nut x, nhom B gia tri y -> nut 100 + y, T = 201
vector<long long> cntA(101, 0), cntB(101, 0);
for (int i = 0; i < n; i++) {
cntA[a[i]]++;
cntB[b[i]]++;
}
int S = 0, T = 201;
G.assign(202, {});
for (int x = 1; x <= 100; x++) {
if (cntA[x] > 0) addEdge(S, x, cntA[x], 0);
if (cntB[x] > 0) addEdge(100 + x, T, cntB[x], 0);
}
for (int x = 1; x <= 100; x++)
for (int y = 1; y <= 100; y++)
if (cntA[x] > 0 && cntB[y] > 0) addEdge(x, 100 + y, n, 2 - score(x, y));
long long c = minCostFlow(S, T, n);
cout << 2LL * n - c << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
b.resize(n);
for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
if (n <= 200) sub1();
else sub2();
return 0;
}
Bình luận