Definitions
Bipartite Graph
A bipartite graph is a graph (G = (V, E)) where the vertex set (V) can be partitioned into two disjoint subsets (V_1) and (V_2) such that every edge connects a vertex in (V_1) to a vertex in (V_2). We refer to (V_1) as the left partition and (V_2) as the right partition.
Matching
A matching in a graph is a subset of edges where no two edges share a common endpoint. The size of a matching equals the number of edges it contains. A maximum matching is a matching of maximum possible size. When a matching covers all vertices on one side of the bipartition, it is called a perfect matching. Every perfect matching is necessarily a maximum matching.
Vertex Cover
A vertex cover is a subset of vertices such that every edge in the graph has at least one endpoint in this subset. The size of a vertex cover equals the number of vertices it contains. A minimum vertex cover is the smallest such subset.
Independent Set
An independent set is a subset of vertices with no edge between any two vertices in the subset. The maximum independent set is the largest such subset.
Maximum Matching in Bipartite Graphs
Maximum matching in bipartite graphs can be computed efficiently using augmenting paths. The Hungarian algorithm processes vertices from one partition sequentially, attempting to find augmenting paths.
When processing a left vertex (u), the algorithm explores unvisited right vertices connected to (u). If an unvisited right vertex (v) is unmatched, we pair (u) with (v). If (v) is already matched to some vertex (w), we recursively try to rematch (w) to a different vertex. This process of reassignment creates alternating paths between matched and unmatched edges.
The edges traversed during this process form an augmenting path or alternating path, characterized by alternating matched and unmatched edges.
Despite its seemingly brute-force approach, the Hungarian algorithm runs in (O(nm)) time complexity.
bool find_match(int left_vertex) {
for (int right_vertex = 1; right_vertex <= n; right_vertex++) {
if (!visited[right_vertex] && graph[left_vertex][right_vertex]) {
visited[right_vertex] = true;
if (partner[right_vertex] == 0 || find_match(partner[right_vertex])) {
partner[right_vertex] = left_vertex;
return true;
}
}
}
return false;
}
Minimum Vertex Cover in Bipartite Graphs
The minimum vertex cover problem in bipartite graphs has an elegant connection to maximum matching.
König's Theorem: In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
Proof: The lower bound follows from the fact that each edge in a matching requires atleast one distinct endpoint in any vertex cover, since matched edges share no endpoints.
For the upper bound, construct a vertex cover as follows: start from all unmatched vertices on the right partition, traverse all alternating paths, and mark visited vertices. The vertex cover consists of all unmarked left vertices and all marked right vertices.
Each matched edge has exactly one endpoint in this set: if a matched left vertex is unmarked, its matched right vertex must be marked (since we reach it via a matched edge), and vice versa.
To verify completeness, suppose an edge ((u, v)) remains uncovered with (u) on the left and (v) on the right. Then (u) is unmarked and (v) is marked. The edge cannot be unmatched, but if it is a matched edge, (v) would only be marked by traversing from (u) via its matched edge, which would mark (u) as well—a contradiction.
Maximum Independent Set in Bipartite Graphs
Vertex covers and independent sets are complementary concepts. The complement of any vertex cover forms an independent set, since if all edges are incident to the cover, no two remaining vertices can be adjacent.
Therefore:
$$\text{Maximum Independent Set Size} = |V| - \text{Minimum Vertex Cover Size}$$
Hall's Theorem
Hall's theorem provides necessary and sufficient conditions for the existence of a perfect matching in bipartite graphs.
Hall's Theorem: A bipartite graph with partitions (V_1) and (V_2) has a perfect matching if and only if for every subset (S \subseteq V_1), its neighbor set (N(S)) satisfies (|N(S)| \geq |S|).
Proof of sufficiency: Assume a matching exists but is not perfect. Let (a) be an unmatched vertex in (V_1). Since the matching is not maximum, there exists an augmenting path starting from (a).
Consider an adjacent vertex (b). If (b) is unmatched, we can augment the matching—contradiction. If (b) is matched to (c), then by Hall's condition applied to ({a, c}), there exists a vertex (d) adjacent to at least one of (a) or (c).
Repeating this argument constructs an alternating path. Since the graph is finite and the matching is not perfect, this process must eventually reach an unmatched vertex, creating an augmenting path and contradicting the maximality of the current matching.
Problem Applications
Problem 1: CF981F Round Marriage
Minimize the maximum distance in a circular arrangement. Use binary search on the answer (P). Connect men and women within distance (P); check whether a perfect matching exists.
After sorting positions and linearizing the circle, the connected interval for each man forms a contiguous range. The condition that fails Hall's theorem corresponds to a continuous interval in the sorted order.
For man (a_i), let ([L_i, R_i]) be his reachable range in the women's array. An interval ((i, j]) violates Hall's theorem when (j - i > R_j - L_i), which rearranges to (L_i - i > R_j - j). Maintain the minimum value of (R_k - k) for (k < i) during iteration.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000 + 10;
const long long INF = 1e18;
int n, circumference;
long long man[MAXN], woman[MAXN];
bool verify(long long dist) {
long long best = INF;
for (int i = n + 1; i <= 3 * n; i++) {
int left = lower_bound(woman + 1, woman + 4 * n + 1, man[i] - dist) - woman;
int right = upper_bound(woman + 1, woman + 4 * n + 1, man[i] + dist) - woman - 1;
if (i - right > best) return false;
best = min(best, i - left);
}
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> circumference;
for (int i = 1; i <= n; i++) cin >> man[i];
for (int i = 1; i <= n; i++) cin >> woman[i];
sort(man + 1, man + n + 1);
sort(woman + 1, woman + n + 1);
for (int i = n + 1; i <= 4 * n; i++) {
woman[i] = woman[i - n] + circumference;
man[i] = man[i - n] + circumference;
}
int lo = 0, hi = circumference, result = 0;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (verify(mid)) {
result = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << result;
return 0;
}
Problem 2: POI2009 LYZ - Ice Skates
Model shoe rental as a matching problem. Each shoe size appears (k) times. Check weather a perfect matching exists between customers and shoes.
The bottleneck for Hall's theorem occurs when a contiguous interval of customers cannot be served. Let (a_i) customers require shoe size (i). An interval ([l, r]) fails Hall's condition when:
$$\sum_{i=l}^{r} a_i > (r - l + 1) \cdot k + d \cdot k$$
Subtracting (k) from each (a_i) transforms this to checking whether any subarray sum exceeds (d \cdot k). A segment tree supporting range additions and maximum subarray queries handles updates efficiently.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 10;
int n, m, k, d;
namespace SegTree {
struct Node {
long long prefix, suffix, total, maxSub;
};
Node combine(Node left, Node right) {
Node res;
res.total = left.total + right.total;
res.prefix = max(left.prefix, left.total + right.prefix);
res.suffix = max(right.suffix, right.total + left.suffix);
res.maxSub = max({left.maxSub, right.maxSub, left.suffix + right.prefix});
return res;
}
Node tree[MAXN << 2];
long long lazy[MAXN << 2];
void build(int idx, int l, int r) {
if (l == r) {
tree[idx] = {-k, -k, -k, -k};
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
tree[idx] = combine(tree[idx << 1], tree[idx << 1 | 1]);
}
void pushDown(int idx) {
if (!lazy[idx]) return;
for (int child : {idx << 1, idx << 1 | 1}) {
tree[child].prefix += lazy[idx];
tree[child].suffix += lazy[idx];
tree[child].total += lazy[idx];
tree[child].maxSub += lazy[idx];
lazy[child] += lazy[idx];
}
lazy[idx] = 0;
}
void update(int idx, int l, int r, int ql, int qr, long long val) {
if (ql <= l && r <= qr) {
tree[idx].prefix += val;
tree[idx].suffix += val;
tree[idx].total += val;
tree[idx].maxSub += val;
lazy[idx] += val;
return;
}
pushDown(idx);
int mid = (l + r) >> 1;
if (ql <= mid) update(idx << 1, l, mid, ql, qr, val);
if (mid < qr) update(idx << 1 | 1, mid + 1, r, ql, qr, val);
tree[idx] = combine(tree[idx << 1], tree[idx << 1 | 1]);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k >> d;
SegTree::build(1, 1, n);
while (m--) {
int size, count;
cin >> size >> count;
SegTree::update(1, 1, n, size, size, count);
cout << (SegTree::tree[1].maxSub > d * k ? "NIE\n" : "TAK\n");
}
return 0;
}
Problem 3: ARC106E Medals
Award medals to employees over multiple days. Each employee (i) works in cycles of (a_i) days and can receive a medal on any day when (\lfloor (d + a_i - 1) / a_i \rfloor) is odd.
The answer has monotonicity, enabling binary search. For each day, define a bitmask of employees who can receive medals. We need (k) medals per day, so a perfect matching exists if every subset (S) of employees satisfies Hall's condition.
Counting days where (P_d \cap S = \emptyset) (no eligible employee in (S) can receive a medal on day (d)) requires the complement: days where all eligible employees lie outside (S). Use SOS DP to compute these counts for all subsets efficiently.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 18;
const int MAXD = 100000 + 10;
const int MAXMASK = (1 << MAXN) + 10;
int n, k;
int cycle[MAXN + 5];
int dayMask[MAXD + 5];
long long dp[MAXMASK];
int bitCount(int mask) {
return mask == 0 ? 0 : bitCount(mask >> 1) + (mask & 1);
}
bool feasible(int days) {
for (int i = 0; i < (1 << n); i++) dp[i] = 0;
for (int d = 1; d <= days; d++) {
dp[dayMask[d]]++;
}
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < (1 << n); mask++) {
if (mask & (1 << i)) {
dp[mask] += dp[mask ^ (1 << i)];
}
}
}
for (int mask = 0; mask < (1 << n); mask++) {
int empCount = bitCount(mask);
long long unavailable = dp[mask ^ ((1 << n) - 1)];
if (empCount * k > days - unavailable) {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> cycle[i];
int maxDays = 2 * n * k;
for (int d = 1; d <= maxDays; d++) {
dayMask[d] = 0;
for (int i = 1; i <= n; i++) {
if (((cycle[i] + d - 1) / cycle[i]) & 1) {
dayMask[d] |= (1 << (i - 1));
}
}
}
int lo = 0, hi = maxDays, ans = 0;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (feasible(mid)) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << ans;
return 0;
}
Problem 4: POJ 6062 Pair
Sort boys by strength and connect eligible pairs. Each boy's reachable girls forms a prefix. Check for perfect matching by detecting intervals violating Hall's theorem.
A suffix of the sorted girls will cause the violation if no perfect matching exists. This reduces to checking whether any prefix sum of (a_i - k) exceeds zero, where (a_i) counts reachable positions.
Maintain prefix sums using a segment tree with range additions and global maximum queries.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300000 + 10;
int n, m, threshold;
int boy[MAXN], girl[MAXN];
namespace SegTree {
int maxVal[MAXN << 2], lazy[MAXN << 2];
void apply(int idx, int val) {
maxVal[idx] += val;
lazy[idx] += val;
}
void pushDown(int idx) {
if (lazy[idx]) {
apply(idx << 1, lazy[idx]);
apply(idx << 1 | 1, lazy[idx]);
lazy[idx] = 0;
}
}
void build(int idx, int l, int r) {
if (l == r) {
maxVal[idx] = -l;
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
maxVal[idx] = max(maxVal[idx << 1], maxVal[idx << 1 | 1]);
}
void rangeAdd(int idx, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
apply(idx, val);
return;
}
pushDown(idx);
int mid = (l + r) >> 1;
if (ql <= mid) rangeAdd(idx << 1, l, mid, ql, qr, val);
if (mid < qr) rangeAdd(idx << 1 | 1, mid + 1, r, ql, qr, val);
maxVal[idx] = max(maxVal[idx << 1], maxVal[idx << 1 | 1]);
}
}
bool cmpDesc(int x, int y) { return x > y; }
int binarySearch(int val) {
int lo = 1, hi = m, pos = 0;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (girl[mid] >= val) {
pos = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return pos;
}
int overflowCount;
void modify(int x, int delta) {
int pos = binarySearch(threshold - x);
if (pos == 0) {
pos = 1;
overflowCount += delta;
}
SegTree::rangeAdd(1, 1, m, pos, m, delta);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> threshold;
SegTree::build(1, 1, m);
for (int i = 1; i <= m; i++) cin >> girl[i];
for (int i = 1; i <= n; i++) cin >> boy[i];
sort(girl + 1, girl + m + 1, cmpDesc);
for (int i = 1; i <= m; i++) modify(boy[i], 1);
int answer = (SegTree::maxVal[1] <= 0 && overflowCount == 0);
for (int start = 2; start + m - 1 <= n; start++) {
modify(boy[start - 1], -1);
modify(boy[start + m - 1], 1);
answer += (SegTree::maxVal[1] <= 0 && overflowCount == 0);
}
cout << answer;
return 0;
}
Problem 5: ARC080F Prime Flip
Transform to a difference array problem. Flipping two positions simultaneously reduces to pairing ones in the difference array. The cost depends on the distance between paired positions:
- Odd prime distance: cost 1
- Even distance (Goldbach's conjecture): cost 2
- Odd composite distance: cost 3
To minimize total cost, maximize pairs at odd prime distance. View odd-indexed positions as left vertices and even-indexed as right vertices. Build edges between positions at odd prime distance and compute maximum matching.
The remaining unmatched positions pair at cost 2 or 3 depending on parity.
#include <bits/stdc++.h>
using namespace std;
const int MAXP = 100 + 10;
int odd[MAXP], even[MAXP], oddCnt, evenCnt;
int positions[MAXP], matchRight[MAXP];
bool edge[MAXP][MAXP], visited[MAXP];
bool isPrime(int x) {
if (x == 1) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
bool augment(int leftIdx) {
for (int rightIdx = 1; rightIdx <= evenCnt; rightIdx++) {
if (!visited[rightIdx] && edge[leftIdx][rightIdx]) {
visited[rightIdx] = true;
if (!matchRight[rightIdx] || augment(matchRight[rightIdx])) {
matchRight[rightIdx] = leftIdx;
return true;
}
}
}
return false;
}
void insertPosition(int x) {
if (x & 1) even[++evenCnt] = x;
else odd[++oddCnt] = x;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> positions[i];
insertPosition(positions[1]);
for (int i = 2; i <= n; i++) {
if (positions[i] > positions[i-1] + 1) {
insertPosition(positions[i-1] + 1);
insertPosition(positions[i]);
}
}
insertPosition(positions[n] + 1);
for (int i = 1; i <= oddCnt; i++) {
for (int j = 1; j <= evenCnt; j++) {
edge[i][j] = isPrime(abs(odd[i] - even[j]));
}
}
int primePairs = 0;
for (int i = 1; i <= oddCnt; i++) {
fill(visited + 1, visited + evenCnt + 1, false);
primePairs += augment(i);
}
int answer = primePairs;
answer += ((oddCnt - primePairs) / 2) * 2;
answer += ((evenCnt - primePairs) / 2) * 2;
answer += ((evenCnt - primePairs) & 1) * 3;
cout << answer << "\n";
return 0;
}