Matroid và giao matroid
Matroid (đồ thị, tuyến tính, phân hoạch, đều), vì sao tham lam tối ưu trên matroid, và thuật toán giao hai matroid bằng đường tăng ngắn nhất trên đồ thị trao đổi với O(r^2 n) lần gọi oracle.
Matroid là một cấu trúc trừu tượng hoá khái niệm "độc lập": tập cạnh không có chu trình, tập vector độc lập tuyến tính, tập phần tử mà mỗi nhóm lấy không quá một số lượng cho trước... Trên một matroid, thuật toán tham lam (sắp theo trọng số rồi lấy nếu còn độc lập) luôn cho đáp án tối ưu, đó là lý do Kruskal và cơ sở XOR đúng. Khi bài toán đòi đồng thời độc lập trong hai matroid (ví dụ "rừng khung lớn nhất mà mỗi màu dùng tối đa một cạnh"), tham lam thất bại, nhưng giao matroid (matroid intersection) vẫn tìm được tập chung lớn nhất trong thời gian đa thức: lần gọi "oracle độc lập", với là số phần tử và là kích thước đáp án, thay vì thử tập con.
Matroid là gì
Một matroid gồm tập nền hữu hạn và họ các tập con của gọi là tập độc lập, thoả ba tiên đề:
- .
- Di truyền: nếu và thì (bỏ bớt phần tử vẫn độc lập).
- Trao đổi: nếu và thì tồn tại sao cho .
Tập độc lập tối đại gọi là cơ sở (basis); theo tiên đề trao đổi mọi cơ sở có cùng kích thước, gọi là hạng . Tổng quát, hạng của một tập là kích thước tập độc lập lớn nhất nằm trong .
Bốn ví dụ hay gặp:
| Matroid | Tập nền | độc lập khi | Oracle kiểm tra |
|---|---|---|---|
| Đồ thị (graphic) | cạnh của một đồ thị | không chứa chu trình (là một rừng) | DSU |
| Tuyến tính (linear, XOR) | các vector, ví dụ số nguyên xem như vector trên | các vector độc lập tuyến tính (không tập con khác rỗng nào XOR bằng ) | cơ sở XOR / khử Gauss |
| Phân hoạch (partition) | phần tử chia thành các nhóm | với mọi nhóm | đếm số phần tử mỗi nhóm |
| Đều (uniform) | phần tử bất kỳ | so sánh kích thước |
Kiểm tra tiên đề trao đổi cho matroid đồ thị: rừng có thành phần, rừng có ít thành phần hơn, nên phải có một cạnh của nối hai thành phần khác nhau của ; thêm cạnh đó vào vẫn là rừng.
Không phải matroid: tập các cặp ghép (matching) của một đồ thị. Trên đường , và đều là cặp ghép, , nhưng thêm cạnh nào của vào cũng đụng đỉnh hoặc . Đây chính là lý do ghép cặp không giải bằng tham lam được, nhưng (như sẽ thấy) ghép cặp hai phía lại là giao của hai matroid.
Tham lam trên matroid
Định lý (Rado, Edmonds). Cho trọng số trên các phần tử. Thuật toán: sắp phần tử theo giảm dần, duyệt lần lượt, thêm vào nếu còn độc lập. Kết quả là cơ sở có tổng trọng số lớn nhất. Ngược lại, nếu một họ tập con có tính di truyền mà thuật toán này đúng với mọi trọng số thì họ đó là một matroid.
Vì sao đúng (phác thảo). Gọi là các phần tử tham lam chọn (theo thứ tự chọn) và giả sử có cơ sở (sắp giảm) tốt hơn. Lấy nhỏ nhất mà . Áp dụng tiên đề trao đổi cho và : có (, nên ) thêm được vào . Nhưng khi đó tham lam đã xét trước và đã phải chọn nó, mâu thuẫn.
Hệ quả quen thuộc:
- Kruskal là tham lam trên matroid đồ thị (sắp tăng dần để được cây khung nhỏ nhất).
- XOR lớn nhất, cơ sở XOR có tổng trọng số lớn nhất là tham lam trên matroid tuyến tính.
- Bài lập lịch "mỗi việc có hạn chót và tiền thưởng, chọn tập việc làm kịp với tổng thưởng lớn nhất" là tham lam trên một matroid (các tập việc lập lịch được tạo thành matroid). Xem thêm Tham lam.
Một mẹo dùng được ngay: nếu bạn chứng minh được ràng buộc của bài là một matroid, tham lam đúng mà không cần lập luận đổi chỗ (exchange argument) riêng.
Giao matroid: bài toán và trực giác
Cho hai matroid và trên cùng tập nền. Tìm tập lớn nhất sao cho và .
Ví dụ: đồ thị có cạnh tô màu, tìm rừng nhiều cạnh nhất mà không hai cạnh nào cùng màu. là matroid đồ thị, là matroid phân hoạch theo màu với . Giao của hai matroid nói chung không là matroid, nên tham lam có thể kẹt (ví dụ bên dưới).
Ý tưởng giống hệt ghép cặp hai phía: bắt đầu từ , lặp lại việc tìm một đường tăng làm tăng thêm ; khi không còn đường tăng thì là lớn nhất.
Đồ thị trao đổi (exchange graph) : mỗi phần tử của là một đỉnh. Với và :
- cạnh nếu (trong , đổi lấy vẫn độc lập);
- cạnh nếu (trong , đổi lấy vẫn độc lập).
Tập nguồn , tập đích .
Một đường đi từ tới xen kẽ phần tử ngoài và trong . Lật đường đi (thêm các , bỏ các ) cho tập mới lớn hơn đúng . Nhìn theo từng matroid:
- Với : được thêm "miễn phí" (vì ), còn mỗi () thay chỗ qua cạnh .
- Với : được thêm miễn phí (vì ), còn mỗi thay chỗ qua cạnh .
Mỗi phép đổi riêng lẻ giữ tính độc lập, nhưng làm nhiều phép đổi cùng lúc thì chưa chắc. Điểm mấu chốt: nếu chọn đường đi ngắn nhất (BFS) thì chắc chắn độc lập trong cả hai matroid.
Phác thảo chứng minh.
- Đường ngắn nhất giữ độc lập. Đường ngắn nhất không có "lối tắt": chẳng hạn không có cạnh với (nếu có, bỏ được một đoạn và đường ngắn hơn), và không đỉnh nào khác trên đường thuộc hay . Bổ đề của Edmonds (thường gọi là bổ đề ghép cặp duy nhất): nếu các cặp đổi là cách ghép duy nhất giữa và trong đồ thị trao đổi của thì độc lập trong . Tính "không lối tắt" chính là điều kiện duy nhất đó. Với (hoặc với ), thêm một phần tử giả vào matroid để quy về cùng bổ đề.
- Không có đường tăng thì tối ưu. Gọi là tập các phần tử đi tới được một đỉnh đích trong . Không có đường tăng nghĩa là . Từ việc không có cạnh nào đi từ ngoài vào , ta suy ra và , tức . Mà với mọi tập độc lập chung và mọi : . Vậy lớn nhất.
Phần 2 cho luôn định lý min-max của Edmonds:
Với ghép cặp hai phía, đây chính là định lý König (cặp ghép lớn nhất bằng phủ đỉnh nhỏ nhất).
Ví dụ chạy tay
Đồ thị đỉnh, cạnh, màu (đỏ, xanh, lục). Tìm rừng lớn nhất mà mỗi màu dùng tối đa một cạnh.
| cạnh | nối | màu |
|---|---|---|
| đỏ | ||
| xanh | ||
| lục | ||
| đỏ |
graph 4 4 1 2 e1(đỏ) 2 3 e2(xanh) 1 3 e3(lục) 3 4 e4(đỏ) highlight red 1-2 3-4 highlight blue 2-3 highlight green 1-3
Tham lam theo thứ tự lấy , lấy , bỏ (tạo chu trình ), bỏ (màu đỏ đã dùng). Kẹt ở , trong khi đáp án đúng có cạnh. Thuật toán giao matroid cũng đi qua đúng hai bước đầu này (đường tăng độ dài : một phần tử vừa là nguồn vừa là đích), rồi ở dựng đồ thị trao đổi:
- Nguồn ( vẫn là rừng): chỉ . ( tạo chu trình.)
- Đích ( vẫn đúng màu): chỉ . ( trùng màu đỏ với .)
- Cạnh ( khi là rừng): , , , .
- Cạnh ( khi đúng màu): , (màu lục còn trống nên bỏ gì cũng được), (bỏ thì màu đỏ trống). Không có vì có hai cạnh đỏ.
dot
digraph {
rankdir=LR;
node [shape=circle];
e4 [label="e4\nnguồn", color=orange];
e3 [label="e3\nđích", color=green];
e1; e2;
e1 -> e3 [color=red, penwidth=2];
e1 -> e4;
e2 -> e3;
e2 -> e4;
e3 -> e1 [style=dashed];
e3 -> e2 [style=dashed];
e4 -> e1 [style=dashed, color=red, penwidth=2];
}
(Nét liền: cạnh của ; nét đứt: cạnh của ; màu đỏ: đường tăng ngắn nhất.)
BFS từ nguồn tìm được . Lật đường đi: thêm , bỏ , thêm . Ta được : cạnh , , là cây khung, ba màu khác nhau.
Ở vòng tiếp theo không còn nguồn (đã là cây khung) nên thuật toán dừng. Kiểm tra bằng định lý min-max: không có đích nào ( màu đỏ đã dùng), nên và .
Chương trình bên dưới với đầu vào
4 4 3
1 2 1
2 3 2
1 3 3
3 4 1
in ra
3
2 3 4
Cài đặt
Khuôn mẫu tổng quát: mỗi matroid là một struct có hai hàm
build(S): nạp một tập độc lập vào oracle;canAdd(x): hỏi có độc lập không (với vừa nạp).
Để hỏi " có độc lập không", ta build(I - y) một lần rồi gọi canAdd(x) cho mọi . Muốn đổi bài, chỉ cần viết struct matroid mới, hàm matroidIntersection giữ nguyên.
Ví dụ minh hoạ: đọc n m k rồi cạnh u v c (), in số cạnh lớn nhất của một rừng dùng mỗi màu tối đa một cạnh và chỉ số các cạnh đó.
#include <bits/stdc++.h>
using namespace std;
// Graphic matroid: a set of edges is independent iff it is a forest.
struct GraphicMatroid {
int n;
vector<pair<int, int>> edges;
vector<int> par;
GraphicMatroid(int n, vector<pair<int, int>> e) : n(n), edges(e), par(n + 1) {}
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
// Load a base set S (assumed independent) into the oracle
void build(const vector<int>& S) {
iota(par.begin(), par.end(), 0);
for (int e : S) par[find(edges[e].first)] = find(edges[e].second);
}
// Is S + x still independent? (S = the set passed to build)
bool canAdd(int x) { return find(edges[x].first) != find(edges[x].second); }
};
// Partition matroid: element x has group grp[x]; at most cap[g] elements per group.
struct PartitionMatroid {
vector<int> grp, cap, cnt;
PartitionMatroid(vector<int> g, vector<int> c) : grp(g), cap(c), cnt(c.size()) {}
void build(const vector<int>& S) {
fill(cnt.begin(), cnt.end(), 0);
for (int e : S) cnt[grp[e]]++;
}
bool canAdd(int x) { return cnt[grp[x]] < cap[grp[x]]; }
};
// Unweighted matroid intersection: returns a maximum common independent set.
// Each matroid M needs build(S) and canAdd(x). O(r) augmentations,
// each costs O(r) builds and O(r * m) canAdd calls.
template <class M1, class M2>
vector<int> matroidIntersection(int m, M1& A, M2& B) {
vector<char> inI(m, 0);
while (true) {
vector<int> I;
for (int i = 0; i < m; i++) if (inI[i]) I.push_back(i);
// Sources: I + x independent in A. Sinks: I + x independent in B.
A.build(I); B.build(I);
vector<char> isSrc(m, 0), isSink(m, 0);
for (int x = 0; x < m; x++) if (!inI[x]) {
isSrc[x] = A.canAdd(x);
isSink[x] = B.canAdd(x);
}
// Exchange graph, y in I, x not in I:
// y -> x if I - y + x independent in A
// x -> y if I - y + x independent in B
vector<vector<int>> adj(m);
for (int y : I) {
vector<int> rest;
for (int z : I) if (z != y) rest.push_back(z);
A.build(rest); B.build(rest);
for (int x = 0; x < m; x++) if (!inI[x]) {
if (A.canAdd(x)) adj[y].push_back(x);
if (B.canAdd(x)) adj[x].push_back(y);
}
}
// BFS from all sources at once, stop at the first sink reached (shortest path)
vector<int> prv(m, -2);
queue<int> q;
for (int x = 0; x < m; x++) if (isSrc[x]) { prv[x] = -1; q.push(x); }
int end = -1;
while (!q.empty() && end < 0) {
int u = q.front(); q.pop();
if (isSink[u]) { end = u; break; }
for (int v : adj[u]) if (prv[v] == -2) { prv[v] = u; q.push(v); }
}
if (end < 0) break; // no augmenting path: I is maximum
for (int v = end; v != -1; v = prv[v]) inI[v] ^= 1; // flip along the path
}
vector<int> I;
for (int i = 0; i < m; i++) if (inI[i]) I.push_back(i);
return I;
}
int main() {
// Input: n m k, then m lines "u v c" (1 <= c <= k).
// Find the largest forest using at most one edge of each color.
int n, m, k;
cin >> n >> m >> k;
vector<pair<int, int>> edges(m);
vector<int> color(m);
for (int i = 0; i < m; i++) {
cin >> edges[i].first >> edges[i].second >> color[i];
color[i]--;
}
GraphicMatroid G(n, edges);
PartitionMatroid P(color, vector<int>(k, 1));
vector<int> I = matroidIntersection(m, G, P);
cout << I.size() << "\n";
for (int e : I) cout << e + 1 << " ";
cout << "\n";
}
import sys
from collections import deque
class GraphicMatroid:
"""A set of edges is independent iff it is a forest."""
def __init__(self, n, edges):
self.n, self.edges = n, edges
def find(self, x):
while self.par[x] != x:
self.par[x] = self.par[self.par[x]]
x = self.par[x]
return x
def build(self, S):
self.par = list(range(self.n + 1))
for e in S:
u, v = self.edges[e]
self.par[self.find(u)] = self.find(v)
def can_add(self, x):
u, v = self.edges[x]
return self.find(u) != self.find(v)
class PartitionMatroid:
"""At most cap[g] elements from each group g."""
def __init__(self, grp, cap):
self.grp, self.cap = grp, cap
def build(self, S):
self.cnt = [0] * len(self.cap)
for e in S:
self.cnt[self.grp[e]] += 1
def can_add(self, x):
return self.cnt[self.grp[x]] < self.cap[self.grp[x]]
def matroid_intersection(m, A, B):
in_i = [False] * m
while True:
I = [i for i in range(m) if in_i[i]]
A.build(I)
B.build(I)
src = [not in_i[x] and A.can_add(x) for x in range(m)]
sink = [not in_i[x] and B.can_add(x) for x in range(m)]
# Exchange graph: y -> x if I-y+x in A, x -> y if I-y+x in B
adj = [[] for _ in range(m)]
for y in I:
rest = [z for z in I if z != y]
A.build(rest)
B.build(rest)
for x in range(m):
if not in_i[x]:
if A.can_add(x):
adj[y].append(x)
if B.can_add(x):
adj[x].append(y)
# Multi-source BFS, stop at the first sink (shortest augmenting path)
prv = [-2] * m
q = deque()
for x in range(m):
if src[x]:
prv[x] = -1
q.append(x)
end = -1
while q:
u = q.popleft()
if sink[u]:
end = u
break
for v in adj[u]:
if prv[v] == -2:
prv[v] = u
q.append(v)
if end < 0:
break
v = end
while v != -1:
in_i[v] = not in_i[v]
v = prv[v]
return [i for i in range(m) if in_i[i]]
def main():
data = sys.stdin.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
edges, color = [], []
for i in range(m):
u, v, c = map(int, data[3 + 3 * i: 6 + 3 * i])
edges.append((u, v))
color.append(c - 1)
I = matroid_intersection(m, GraphicMatroid(n, edges), PartitionMatroid(color, [1] * k))
print(len(I))
print(" ".join(str(e + 1) for e in I))
main()
Độ phức tạp
Gọi và là kích thước đáp án ().
- Số vòng tăng: mỗi vòng tăng , nên có tối đa vòng (vòng cuối không tìm thấy đường).
- Mỗi vòng: lần
build(một lần cho , một lần cho mỗi ) và lầncanAddđể dựng đồ thị trao đổi; đồ thị có cạnh nên BFS cũng tốn . - Tổng: lần gọi oracle cộng lần
build. Với matroid đồ thị ( đỉnh),buildtốn vàcanAddgần nhờ DSU, nên tổng khoảng . Với matroid XOR bit, mỗi oracle tốn , tổng . - Bộ nhớ: cho danh sách kề của đồ thị trao đổi (có thể bỏ, sinh cạnh ngay trong BFS, để còn nhưng phải gọi oracle lại).
Thử thực tế: , cạnh, màu, đáp án , chương trình C++ chạy khoảng giây. Với cỡ vài nghìn thì cần các cải tiến ở mục Biến thể.
⚠️ Lỗi thường gặp
- Dùng DFS hoặc đường tăng bất kỳ thay vì đường ngắn nhất. Triệu chứng: tập kết quả có chu trình hoặc trùng màu, hoặc đáp án lớn hơn thực tế. Lý do: chỉ đường không lối tắt mới bảo đảm lật xong vẫn độc lập. Luôn dùng BFS nhiều nguồn, dừng ở đích đầu tiên lấy ra khỏi hàng đợi, và truy vết bằng mảng cha của BFS.
- Đảo chiều cạnh của hai matroid. Quy ước phải nhất quán: nguồn theo thì cạnh đi từ sang , còn cạnh đi từ sang , đích theo . Lẫn một chiều là thuật toán sai mà vẫn chạy ra số trông hợp lý; hãy so với brute force trên bộ nhỏ.
- Kiểm tra thay vì khi dựng cạnh. Cạnh của đồ thị trao đổi hỏi về tập sau khi bỏ . Phải
build(I - y)rồi mớicanAdd(x), không dùng lại oracle đã nạp . - Quên đường độ dài 0. Phần tử vừa là nguồn vừa là đích thì chỉ cần thêm thẳng. Cài đặt BFS ở trên xử lý tự nhiên vì kiểm tra "là đích" ngay khi lấy đỉnh ra khỏi hàng đợi, kể cả với đỉnh nguồn.
- Nghĩ tham lam là đủ. Tham lam trên giao hai matroid chỉ bảo đảm được ít nhất một nửa đáp án (ví dụ trên: so với ). Nếu bài có hai ràng buộc kiểu matroid chồng lên nhau, đó là tín hiệu cần giao matroid (hoặc luồng).
- Mở rộng sang ba matroid. Giao ba matroid là NP-khó (đường đi Hamilton có hướng biểu diễn được như vậy). Đừng cố tổng quát hoá thuật toán cho ràng buộc.
- Khuyên (self-loop) và cạnh lặp. Khuyên không bao giờ độc lập trong matroid đồ thị, DSU tự loại nó (cùng thành phần). Không được "bỏ qua" khuyên bằng cách coi nó độc lập.
- Ước lượng độ phức tạp quá lạc quan. với đã là . Đọc kỹ giới hạn: giao matroid ngây thơ hợp với vài trăm đến khoảng , vài trăm.
Ứng dụng kinh điển
Cây khung nhiều màu (graphic × partition). Mỗi cạnh có một màu, màu được dùng tối đa cạnh. là matroid đồ thị, là matroid phân hoạch theo màu với giới hạn . Có cây khung thoả mãn khi và chỉ khi đáp án bằng . Code ở trên chỉ cần đổi vector<int>(k, 1) thành mảng giới hạn.
Cơ sở XOR có màu (linear × partition). Cho các số có màu, chọn nhiều số nhất độc lập tuyến tính (trên ) mà mỗi màu tối đa một số. Chỉ cần thay GraphicMatroid bằng oracle cơ sở XOR:
// Linear matroid over GF(2): a set of numbers is independent iff
// no non-empty subset XORs to 0 (i.e. they are linearly independent).
struct XorMatroid {
vector<long long> val;
long long basis[60];
XorMatroid(vector<long long> v) : val(v) {}
bool reduce(long long x, bool insert) {
for (int b = 59; b >= 0; b--) {
if (!(x >> b & 1)) continue;
if (!basis[b]) {
if (insert) basis[b] = x;
return true; // x is independent of the basis
}
x ^= basis[b];
}
return false; // x reduced to 0
}
void build(const vector<int>& S) {
fill(basis, basis + 60, 0);
for (int e : S) reduce(val[e], true);
}
bool canAdd(int x) { return reduce(val[x], false); }
};
Gọi XorMatroid X(a); PartitionMatroid P(color, vector<int>(k, 1)); matroidIntersection(m, X, P);. Số không bao giờ độc lập, oracle tự loại nó.
Ghép cặp hai phía là trường hợp đặc biệt (partition × partition). Tập nền là các cạnh của đồ thị hai phía. : mỗi đỉnh trái thuộc tối đa một cạnh được chọn (phân hoạch cạnh theo đầu trái, ); : tương tự với đầu phải. Tập độc lập chung chính là cặp ghép, và đường tăng trong đồ thị trao đổi tương ứng với đường tăng xen kẽ quen thuộc. Thực tế ghép cặp nên dùng Kuhn hoặc Hopcroft-Karp cho nhanh, nhưng góc nhìn này giúp nhận ra rằng giao matroid là "ghép cặp tổng quát hoá".
Cây khung có hướng gốc (arborescence). Chọn cung sao cho bỏ hướng là cây khung (: matroid đồ thị trên đồ thị vô hướng tương ứng) và mỗi đỉnh khác gốc có đúng một cung vào, gốc không có cung vào (: phân hoạch theo đỉnh đích, , cung vào gốc có ). Bản có trọng số của bài này thường giải bằng thuật toán Chu-Liu/Edmonds nhanh hơn.
Biến thể / Mở rộng
- Giao matroid có trọng số. Mỗi phần tử có trọng số , tìm tập độc lập chung có tổng lớn nhất. Gán trọng số cho đỉnh của đồ thị trao đổi: mang chi phí (thêm vào thì được ), mang chi phí (bỏ ra thì mất ). Mỗi vòng tìm đường từ tới có tổng chi phí nhỏ nhất, hoà thì lấy đường ít cạnh nhất. Vì có chi phí âm nên dùng Bellman-Ford / SPFA (đồ thị trao đổi không có chu trình âm khi đang tối ưu cho kích thước của nó). Sau vòng thứ , là tập độc lập chung kích thước có trọng số lớn nhất; đáp án không giới hạn kích thước là giá trị tốt nhất qua mọi . Ý tưởng giống hệt luồng chi phí nhỏ nhất tăng dần theo đường ngắn nhất.
- Tăng tốc. Thuật toán Cunningham tìm nhiều đường tăng ngắn nhất rời nhau mỗi pha (giống Hopcroft-Karp), giảm còn lần gọi oracle. Với matroid đồ thị và phân hoạch còn có thể dựng cạnh nhanh hơn: với đồ thị, khi và chỉ khi có chu trình đi qua (hoặc là rừng), nên chỉ cần tìm đường trên cây.
- Hợp matroid (matroid union / partition). Câu hỏi "phủ được bằng tập độc lập không", hay "đồ thị có cây khung rời cạnh không", quy về giao matroid: nhân bản mỗi phần tử lần, lấy giao của "hợp rời bản sao của " với matroid phân hoạch "mỗi phần tử gốc chọn tối đa một bản".
- Tính chất trao đổi tự nó đã mạnh. Nhiều bài không cần giao matroid đầy đủ, chỉ cần tiên đề trao đổi: ví dụ "số cạnh đỏ trong một cây khung nhận mọi giá trị trong một đoạn " vì từ một cây khung có thể đổi từng cạnh một làm số cạnh đỏ thay đổi đúng .
Bài tập luyện
Hiện CTOJ chưa có bài đòi đúng giao matroid tổng quát; các bài dưới đây luyện các khối xây dựng: nhận ra matroid, tham lam trên matroid, tính chất trao đổi và các oracle (DSU, cơ sở XOR).
- Mạng công ty (dhbb2410comnet): (Khó) Chọn dây rẻ nhất để đấu nối lại sao cho gỡ chúng ra không làm tăng số thành phần liên thông. Các tập dây như vậy là tập độc lập của matroid đối ngẫu của matroid đồ thị, nên tham lam theo chi phí (tương đương dựng rừng khung lớn nhất) là tối ưu.
- Mạng truyền thông (voi14_aznet): (Rất khó) Cây khung gồm cạnh của hai công ty, chi phí chỉ phụ thuộc số cạnh mỗi bên. Dùng tính chất trao đổi của cây khung để chứng minh các số lượng đạt được là một đoạn liên tục, rồi dựng cây đúng số lượng bằng DSU.
- XOR cực đại tập con (xorbasis): (Rất khó) Dựng cơ sở XOR, chính là oracle độc lập của matroid tuyến tính dùng trong
XorMatroidở trên, rồi tham lam từ bit cao xuống. - Cơn Ác Mộng Euclid (eucz2): (Rất khó) Vector trên có tối đa hai bit : nhận ra matroid tuyến tính này thực chất là matroid đồ thị (thêm một đỉnh giả), rồi tham lam theo thứ tự chỉ số để được cơ sở nhỏ nhất theo thứ tự từ điển.
- Bàn thắng (icpc23mng): (Chuyên gia) Tập khung thành mà người đi sau thắng được cùng lúc (điều kiện Hall) là một matroid ghép cặp (transversal matroid), nên tham lam theo điểm giảm dần là tối ưu; kết hợp với lập luận về nước đi của người đi trước và quy hoạch động xác suất.
Bình luận