CSP暑期集训 Day05 - 最小生成树与二分图

DAY 05

最小生成树与二分图

CSP 暑期集训 · MST & Bipartite Graph · 算法+性质+建模全覆盖

🌳

Kruskal + Prim

MST算法+性质+建模

📐

MST性质

切割性质+环性质+判定

🎨

二分图判定

染色法+奇环检测

💕

匈牙利+König

匹配+四大量+建模

✏️ 📎

🏗️ 城市修路问题：n 个城市，m 条可修建的道路，每条路有不同的费用。求：最少花多少钱让所有城市互相连通？

🎯 最小生成树（Minimum Spanning Tree, MST）
给定无向连通图 G=(V,E)，生成树是包含所有顶点的无环连通子图。
最小生成树是所有生成树中边权之和最小的那棵。
关键性质：n 个顶点的生成树恰好有 n-1 条边。

💡 Kruskal 贪心策略

⚡ 核心思想：将所有边按权值从小到大排序，依次考虑每条边。
若加入该边不会形成环，就加入生成树；否则跳过。直到选出 n-1 条边。

📐 贪心正确性证明（反证法）

定理：Kruskal 算法得到的生成树一定是最小生成树。

证明（反证法）：
① 设 Kruskal 选出的边集为 T，假设 T 不是 MST，存在更优的 MST T'。
② 设 e 是 T 中第一条不在 T' 中的边（按加入顺序）。
③ 将 e 加入 T'，必形成一个环 C。
④ 环 C 上必存在一条边 e' 不在 T 中（否则 T 本身有环，矛盾）。
⑤ 因为 Kruskal 选了 e 而不是 e'，所以 w(e) ≤ w(e')。
⑥ 用 e 替换 T' 中的 e'，得到新树 T'' = T' - e' + e。
⑦ w(T'') = w(T') - w(e') + w(e) ≤ w(T')。
⑧ 这说明 T'' 不比 T' 差。反复替换可得 w(T) ≤ w(T')，矛盾！ ✅

1

边按权排序

→

2

取最小边

→

3

并查集判环

→

4

不环则加入

→

5

n-1条完成

🔧 并查集核心操作：Find + Union

并查集（Union-Find）维护若干不相交集合，支持两种操作：
• Find(x)：返回 x 所在集合的代表元素（根节点）
• Union(x, y)：合并 x 和 y 所在的集合
通过路径压缩和按秩合并两个优化，每次操作均摊 O(α(n))。

🖼️ SVG图解：路径压缩 + 按秩合并

💻 并查集完整实现

int fa[N], rnk[N];  // fa[]=父节点, rnk[]=秩（树高上界）

void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;    // 初始：每个节点独立成集合，自己是根
        rnk[i] = 0;   // 初始：树高为0（只有1个节点）
    }
}

int find(int x) {
    // 路径压缩：递归找到根后，把沿途所有节点的fa直接指向根
    return fa[x] == x ? x : fa[x] = find(fa[x]);
    // 等价于：if(fa[x]==x) return x; return fa[x]=find(fa[x]);
}

void unionSet(int x, int y) {
    int fx = find(x), fy = find(y);  // 先找到各自的根
    if (fx == fy) return;            // 已在同一集合，无需合并
    // 按秩合并：矮树挂到高树下
    if (rnk[fx] < rnk[fy]) swap(fx, fy);  // 保证fx是高树的根
    fa[fy] = fx;                            // fy挂到fx下面
    if (rnk[fx] == rnk[fy]) rnk[fx]++;     // 同高合并，高度+1
}

💡 路径压缩 + 按秩合并一起使用时，每次操作的时间复杂度为 O(α(n))，其中 α 是反阿克曼函数。对于所有实际规模（n ≤ 10⁷），α(n) ≤ 4，可以认为是常数时间！

🖼️ SVG图解：Kruskal 逐步选边过程

💻 完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5005, M = 200005;
int fa[N], rnk[N], n, m;  // fa=并查集父节点, rnk=秩

struct Edge { int u, v, w; };  // 边结构体：起点、终点、权值
vector<Edge> edges;  // 存储所有边

bool cmp(const Edge& a, const Edge& b) {
    return a.w < b.w;  // 按边权从小到大排序
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);  // 路径压缩
}

int kruskal() {
    sort(edges.begin(), edges.end(), cmp);  // 第一步：按边权排序
    for (int i = 1; i <= n; i++) {
        fa[i] = i;   // 初始化：每个节点自成一体
        rnk[i] = 0;  // 初始秩为0
    }
    int ans = 0, cnt = 0;  // ans=总权值, cnt=已选边数
    for (auto& e : edges) {
        int fu = find(e.u), fv = find(e.v);  // 查找两端点的根
        if (fu != fv) {           // 不同集合→不形成环→加入MST
            if (rnk[fu] < rnk[fv]) swap(fu, fv);  // 按秩合并
            fa[fv] = fu;           // 矮树挂到高树下
            if (rnk[fu] == rnk[fv]) rnk[fu]++;  // 同高则增高
            ans += e.w;            // 累加边权
            if (++cnt == n - 1) break;  // 选够n-1条边即可
        }
    }
    return cnt == n - 1 ? ans : -1;  // 不连通返回-1
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        edges.push_back({u, v, w});  // 读入每条边
    }
    int ans = kruskal();
    if (ans == -1) puts("impossible");  // 图不连通
    else printf("%d\n", ans);  // 输出MST权值和
}

📝 洛谷 P3366 【模板】最小生成树
上面的 Kruskal 代码即为 P3366 的标准解法。该题 n≤5000, m≤2×10⁵，Kruskal O(m log m) 可通过，瓶颈在排序。

⚠️ Kruskal 常见错误：
① 忘记排序：Kruskal 的前提是边按权从小到大，漏掉 sort 会 WA。
② 忘记初始化并查集：fa[i]=i 必须在 kruskal 函数内做。
③ 不连通判断：如果选完所有边仍未凑够 n-1 条，说明图不连通。
④ 边权相同时的排序稳定性：C++ sort 不保证稳定，但 MST 不要求相同权值的特定顺序。

📐 Kruskal 复杂度分析

总复杂度 = 排序 + m次并查集操作

T(n, m) = T_sort + T_UF

第一项：排序
对 m 条边排序，比较排序下界为 Ω(m log m)。

T_sort = O(m log m)

第二项：并查集操作
共 m 条边，每条边最多 2 次 Find + 1 次 Union = O(m) 次操作。
单次 Find/Union 的均摊复杂度（路径压缩 + 按秩合并）：

O(α(n))

其中 α(n) 是反阿克曼函数（Inverse Ackermann Function）。

阿克曼函数 A(m,n) 增长极快：
A(1,n) = n+2, A(2,n) = 2n+3, A(3,n) = 2ⁿ⁺³-3, A(4,n) = 2↑↑(n+3)-3
反阿克曼函数 α(n) = min{k : A(k,k) ≥ n}
对于所有实际 n（甚至 n = 2⁶⁵⁵³⁶），α(n) ≤ 4。

T_UF = O(m · α(n)) ≈ O(m)

合并：

T(n, m) = O(m log m) + O(m · α(n)) = O(m log m)

排序是瓶颈。并查集操作几乎线性。

📊 复杂度对比总结

排序O(m log m)

并查集初始化O(n)

m次FindO(m·α(n))

总复杂度O(m log m)

空间O(n + m)

操作	次数	单次代价	总计
sort 排序	1	O(m log m)	O(m log m)
初始化并查集	1	O(n)	O(n)
Find 查找	2m	O(α(n))	O(m·α(n))
Union 合并	≤ n-1	O(α(n))	O(n·α(n))
总计			O(m log m)

💡 实际竞赛中：α(n) 可以当作常数。Kruskal 的瓶颈在排序。如果边已经排好序（如增量加边），Kruskal 可以优化到 O(m·α(n)) ≈ O(m)。

📌 Prim vs Dijkstra 思想对比

对比项	Dijkstra	Prim
维护集合	S = 已确定最短路的节点	S = 已在MST中的节点
dist含义	s到u的最短距离	MST集合到u的最小边权
松弛方式	dist[v] = min(dist[v], dist[u]+w)	dist[v] = min(dist[v], w(u,v))
贪心选择	选dist最小的未确定节点	选dist最小的未加入节点
结果	单源最短路径树	最小生成树

💡 Prim 算法步骤

⚡ ① 初始化：任选一个起点加入 MST 集合 S，dist[起点]=0，其余 dist=∞
② 每次从 V-S 中选 dist 最小的节点 u 加入 S
③ 用 u 更新所有邻居 v 的 dist[v] = min(dist[v], w(u,v))
④ 重复直到所有节点都在 S 中

💻 Prim 优先队列优化代码

typedef pair<int,int> pii;  // (dist, node)
vector<pii> adj[N];  // 邻接表：adj[u] = {(v,w), ...}
int dist[N];  // dist[u] = MST集合到u的最小边权
bool vis[N];  // vis[u] = u是否已加入MST

int prim() {
    memset(dist, 0x3f, sizeof(dist));  // 初始：所有dist=∞
    dist[1] = 0;  // 从节点1开始，dist[1]=0（起点无边权代价）
    // 小根堆：按dist从小到大取节点
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 1});  // 起点入队
    int ans = 0, cnt = 0;  // ans=MST总权值, cnt=已加入节点数

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();  // 取dist最小的节点
        if (vis[u]) continue;  // 已加入MST的跳过（惰性删除）
        vis[u] = true;          // 标记加入MST
        ans += d;                // 累加边权（注意：是d不是dist[u]+d！）
        cnt++;
        for (auto& [v, w] : adj[u]) {  // 遍历u的所有邻居
            if (!vis[v] && w < dist[v]) {  // 关键：w < dist[v]
                dist[v] = w;       // 更新为边权（不是dist[u]+w！）
                pq.push({dist[v], v});  // 入队等待处理
            }
        }
    }
    return cnt == n ? ans : -1;  // n个节点全加入=连通
}

📝 洛谷 P3366 【模板】最小生成树
上面给出的 Prim 代码正是 P3366 的解法。该题 n≤5000, m≤2×10⁵，Prim 堆优化版 O((n+m)log n) 和 Kruskal O(m log m) 均可通过。

💡 P3366 选哪个算法？
• n≤5000, m≤2×10⁵ → 两算法均可，Kruskal 代码更短
• 稠密图（m ≈ n²）→ Prim 朴素版 O(n²) 更快
• 稀疏图（m ≈ n）→ Kruskal 或 Prim 堆优化均可

⚠️ Prim 易错点：
① 松弛公式不同！dist[v] = w(u,v)，不是 dist[v] = dist[u] + w(u,v)！
因为 dist 含义不同：Prim 维护的是「集合到 v 的最小边权」，不是路径长度。
② ans += d 而非 ans += dist[u]：因为 d 就是选中的那条边的权值。
③ 起点 dist=0：起点不需要「边」连入，所以代价为0。

🖼️ 例题：4节点5边，Prim求MST

📊 Prim vs Kruskal 适用场景

对比项	Kruskal	Prim（堆优化）	Prim（朴素）
时间复杂度	O(m log m)	O((n+m) log n)	O(n²)
适用场景	稀疏图（m小）	通用	稠密图（m≈n²）
实现难度	⭐⭐ 排序+并查集	⭐⭐ 类似Dijkstra	⭐ 简单循环
空间复杂度	O(m) 存边	O(n+m) 邻接表	O(n²) 邻接矩阵
关键区别	按边贪心	按节点贪心	按节点贪心

经验法则：
• m ≈ n（稀疏图）→ Kruskal 简单高效
• m ≈ n²（稠密图）→ Prim 朴素版 O(n²) 最优
• 一般情况 → Prim 堆优化或 Kruskal 均可

📐 Prim 朴素版复杂度

朴素Prim（邻接矩阵 + 线性扫描）：

外层循环 n 次（每次加入一个节点）：
① 线性扫描 dist[] 找最小值：O(n)
② 更新邻居 dist[]：O(n)（遍历整行邻接矩阵）

T_naive = n × (O(n) + O(n)) = O(n²)

注意：与边数 m 无关！对于稠密图（m ≈ n²），O(n²) = O(m)，已是最优。

📐 Prim 堆优化版复杂度

堆优化Prim（优先队列 + 邻接表）：

每个节点最多入队一次（被选中时）+ 可能入队多次（dist被更新时）：
① 每次 pop：O(log n)，共最多 O(n + m) 次 pop（含惰性删除）
② 每次 push：O(log n)，每条边最多触发一次 push → O(m log n)
③ 每个节点加入MST后更新邻居：遍历所有边共 O(m) 次

T_heap = O((n + m) log n)

与 Dijkstra 堆优化对比：
Dijkstra: O((n + m) log n) — 几乎一模一样！
区别只在松弛方式（Prim: dist[v]=w，Dijkstra: dist[v]=dist[u]+w）

📊 三种MST方法完整对比

方法	时间	空间	最佳场景
Kruskal	O(m log m)	O(n+m)	m ≈ n（稀疏图）
Prim 堆优化	O((n+m)log n)	O(n+m)	通用/中等密度
Prim 朴素	O(n²)	O(n²)	m ≈ n²（稠密图）

当 m ≈ n 时：
Kruskal: O(n log n) | Prim 堆: O(n log n) | Prim 朴素: O(n²)
→ Kruskal 和 Prim 堆相当，Prim 朴素太慢

当 m ≈ n² 时：
Kruskal: O(n² log n) | Prim 堆: O(n² log n) | Prim 朴素: O(n²)
→ Prim 朴素版最快！因为避免了 log n 的堆操作开销

📐 MST的两大核心性质

切割性质（Cut Property）：
对于图的任意一个割（将顶点分为S和T两部分），跨越割的边中权值最小的边一定属于某棵MST。
→ 这是Kruskal和Prim贪心正确性的理论基础。

环性质（Cycle Property）：
对于图中的任意一个环，环上权值最大的边一定不属于任何MST（除非有重边）。
→ 可用于排除边：如果一条边是某个环上的严格最大边，它一定不在MST中。

切割性质：割的最小边 ∈ MST | 环性质：环的最大边 ∉ MST

📊 CSP-S中MST常见题型

题型	核心思路	代表题目
直接求MST	Kruskal / Prim 模板	P3366, P2330, P1111
MST + 并查集连通性	Kruskal过程中判断何时全连通	P1111, P1991
MST + 二分答案	二分某个值，用MST/连通性验证	P1991
MST变形（选边限制）	排序+贪心，选满足条件的最小边集	P1194
判断边是否在MST中	环性质：该边是否为某环的严格最大边	CSP-S真题常见
次小生成树	枚举非MST边替换MST路径上的最大边	进阶考点

🔍 MST性质应用：判断边是否属于MST

方法一（枚举法）：对每条边 e=(u,v,w)，从图中去掉 e 后求 u→v 路径上的最大边权 max_w。
• 若 w < max_w → e 在所有 MST 中
• 若 w = max_w → e 在部分 MST 中
• 若 w > max_w → e 不在任何 MST 中

方法二（MST树上判定）：先求一棵 MST，对非树边 e=(u,v,w)，找到树上 u→v 路径的最大边 max_w。
• w > max_w → MST 唯一（该边不会替换任何树边）
• w = max_w → 有多棵 MST

🏗️ CSP-S真题建模：P1991 无线通讯网

📌 题目：S个卫星频道，W个哨所，每个哨所有坐标。有卫星的哨所可以无线通信（距离不限），否则需要无线电，距离越远功率越大。求最小需要的无线电功率 D。

建模：① 求完全图的 MST（边权=欧几里得距离）
② MST 有 W−1 条边，S个卫星可以「免费」连接 S−1 条最远的边
③ 去掉 MST 上最大的 S−1 条边，剩余的最大边就是答案 D

答案 = MST第 (W−S) 大的边（从小到大排序后）

⚠️ MST易错点总结

CSP-S实战注意：
① 不连通图没有生成树！先判断连通性
② 重边取最小权（MST不会选重边中更大的）
③ 自环不影响 MST（自环一定不在MST中）
④ 边权全部相同时，任意生成树都是MST
⑤ MST的总权值唯一，但MST本身不一定唯一

⚓ 核心总结：MST不只是模板！CSP-S常考「MST+二分答案」「MST+并查集连通性」「MST性质判定」等变形题。

🎯 二分图（Bipartite Graph）
如果图 G=(V,E) 的顶点集 V 可以被分成两个不相交的子集 L 和 R，使得每条边的两个端点分别属于 L 和 R（即同侧无边），则称 G 为二分图。
生活场景：男生一组、女生一组，只有男女之间才有关系（边）；棋盘黑白染色，棋子只能从黑格跳到白格。

🔑 核心定理

定理：图 G 是二分图 ⟺ G 中不含奇数长度的环（奇环）。

证明（必要性）：
① 假设 G 是二分图，顶点分为 L 和 R。
② 任取一个环 v₁→v₂→...→vₖ→v₁。
③ 不妨设 v₁∈L，则 v₂∈R, v₃∈L, v₄∈R...交替分布。
④ 回到 v₁ 时，下标为偶数才在 L → k 必须是偶数。
⑤ 所以不存在奇环。 ✅

证明（充分性）：连通图中无奇环 → 从任一点 BFS 染色，距离为偶数的染蓝色、奇数的染红色，不会冲突 → 是二分图。 ✅

🖼️ 二分图示例

💡 关键性质：树一定是二分图！因为树无环，自然无奇环。实际应用中，很多图论问题可以先用染色法快速判断是否为二分图，再用专门的二分图算法。

🖼️ 染色过程图解

💻 染色法判定二分图（DFS版）

// 染色法判定二分图 — DFS实现
// 核心思想：交替染色，发现冲突则有奇环

int color[N];  // 0=未染色, 1=蓝色, 2=红色
vector<int> adj[N];  // 邻接表

bool dfs_color(int u, int c) {
    color[u] = c;  // 当前节点染色 c
    for (int v : adj[u]) {  // 遍历所有邻居
        if (color[v] == 0) {  // 未染色：染相反颜色继续DFS
            if (!dfs_color(v, 3 - c))  // 3-c实现1↔2交替
                return false;  // 子树中发现了冲突
        } else if (color[v] == c) {  // 已染色且颜色相同 → 冲突!
            return false;  // 说明有奇环，不是二分图
        }
    }
    return true;  // 该连通分量无冲突
}

bool isBipartite(int n) {
    memset(color, 0, sizeof(color));  // 清空所有颜色
    for (int i = 1; i <= n; i++) {  // 遍历所有节点（处理不连通图）
        if (color[i] == 0) {  // 未访问的节点作为新连通分量的起点
            if (!dfs_color(i, 1))  // 从蓝色(1)开始染色
                return false;
        }
    }
    return true;  // 所有连通分量都无冲突 → 是二分图
}

💡 注意：图可能不连通！需要对每个未染色节点都启动一次 DFS。每次染色 3-c 的技巧：c=1 时 3-1=2，c=2 时 3-2=1，完美实现蓝红交替。

⏱️ 复杂度分析

染色法时间复杂度证明：

① 每个节点恰好被访问一次 → 节点处理总时间 O(n)
② 每条边 (u,v) 被检查两次（u→v 和 v→u） → 边处理总时间 O(m)
③ 每个节点染色操作 O(1)，邻居遍历 O(degree(u))

T(n, m) = Σᵤ O(1) + Σᵤ O(deg(u)) = O(n) + O(2m) = O(n + m)

空间复杂度：O(n + m)（邻接表存储 + color数组 + DFS递归栈）

时间O(n + m)

空间O(n + m)

最优性线性最优

📝 P1330 封锁阳光大学
河蟹不能相邻放置。问能否放置，能则输出最少数量。

分析： ① 不能相邻 = 相邻节点不能同时选 → 本质是二分图染色
② 先判断是否为二分图（染色法），如果不是 → 输出 "Impossible"
③ 如果是 → 每个连通分量取颜色数量少的那侧
④ 答案 = Σ 每个连通分量 min(|蓝色|, |红色|)

🖼️ 染色法应用图解

⚠️ 易错点：
① 图可能不连通！必须遍历所有未染色节点启动 DFS
② 自环 → 自己和自己同色 → 一定不是二分图
③ 重边不影响二分图判定（不影响奇偶性）

🎯 匹配与最大匹配
匹配（Matching）：边集 M ⊆ E，使得 M 中任意两条边不共享端点。
最大匹配：包含边数最多的匹配。
完美匹配：所有顶点都被匹配的匹配（最大匹配的特例）。
生活场景：n 个男生和 m 个女生，某些男女之间互相愿意配对，每人最多配一个 → 最多能配对多少对？

💡 匈牙利算法核心思想

⚡ 增广路思想：
① 从左部每个未匹配点出发，尝试找匹配（DFS）
② 如果右部某个候选者还没被匹配 → 直接配对 ✅
③ 如果右部候选者已有配对 → 让ta现有对象"让位"，即递归地尝试给现有对象找新配对
④ 一句话："如果没匹配就匹配，如果已匹配就尝试让之前的换人"

🖼️ 增广路图解

⚠️ 易错点：visited 数组没清空！
匈牙利算法每个左部点开始 dfs 之前，必须 memset(visited, 0, sizeof visited)。
以上面为例：Step② 的 dfs 结束后 visited={g1:T, g2:T}，如果 Step③ 处理 b3 时没清空，b3 唯一的邻居 g2 已被标记 → b3 一步都走不出去 → 本应匹配数=3 却得到 2。
口诀：每个 boy 出发前，visited 全部归零！

💻 匈牙利算法模板

// 匈牙利算法 — 求二分图最大匹配
// 左部点 1..n，右部点 1..m

vector<int> adj[N];  // adj[u]: 左部点u的候选右部点列表
int match[N];        // match[v]: 右部点v当前匹配的左部点（0=未匹配）
bool vis[N];         // vis[v]: 本轮DFS中右部点v是否已被尝试过

bool dfs(int u) {  // 尝试为左部点u找匹配
    for (int v : adj[u]) {  // 遍历u的所有候选右部点v
        if (vis[v]) continue;  // 本轮已尝试过v，跳过（防死循环）
        vis[v] = true;  // 标记v本轮已访问
        // 如果v还没匹配，或者v的当前对象能找到新对象
        if (match[v] == 0 || dfs(match[v])) {
            match[v] = u;  // v和u配对！
            return true;   // 成功找到增广路
        }
        // 否则继续尝试u的下一个候选点
    }
    return false;  // u所有候选点都失败了
}

int hungarian(int n) {
    int ans = 0;  // 最大匹配数
    memset(match, 0, sizeof(match));  // 清空所有匹配
    for (int i = 1; i <= n; i++) {  // 枚举每个左部点
        memset(vis, false, sizeof(vis));  // 每轮DFS前清空访问标记
        if (dfs(i)) ans++;  // 如果找到增广路 → 匹配数+1
    }
    return ans;  // 返回最大匹配数
}

🔍 代码逐行解读

关键变量说明：
• match[v]：右部点 v 当前匹配了哪个左部点（0 表示空闲）
• vis[v]：在当前这轮 DFS 中，右部点 v 是否已被尝试过
• dfs(u)：为左部点 u 找匹配 → 遍历候选 v → 若 v 空闲则直接配 → 若 v 已配则递归让 match[v] 换人
• 每轮主循环前清空 vis：保证每轮 DFS 独立，不会因上一轮的标记而漏选

📝 P3386 【模板】二分图最大匹配
给定二分图，左部 n 个点，右部 m 个点，e 条边。求最大匹配数。

分析： ① 直接用匈牙利算法模板
② 建图：读入每条边 (u,v)，加入 adj[u]
③ 调用 hungarian(n) 即得答案
④ 时间 O(n × m)，对于 n,m ≤ 500 完全够用

💡 记忆技巧：匈牙利算法的核心就是一个递归函数 dfs(u)：
"我来帮你找对象 → 这个可以 → 但ta有主了 → 让ta的对象换一个人 → 递归..."
本质是不断尝试让位，直到找到一条增广路或者彻底失败。

⏱️ 复杂度分析

匈牙利算法时间复杂度证明：

① 主循环枚举每个左部点：共 n 轮
② 每轮 DFS 最坏情况：每个右部点最多被访问一次 → O(m + e)
（m 为右部点数，e 为边数，每条边最多遍历一次）
③ 每轮前 memset(vis) 开销 O(m)

T(n, m, e) = n × O(m + e) = O(n × (m + e))

通常简记为 O(n × e) 或 O(V × E)。

空间复杂度：O(n + m + e)（邻接表 + match数组 + vis数组）

时间O(n × e)

空间O(n + m + e)

适用规模n,m ≤ 1000

📊 Day05 全部算法复杂度对比

算法	解决的问题	时间复杂度	空间复杂度	核心思想
Kruskal	最小生成树	O(m log m)	O(n + m)	贪心选边+并查集判环
Prim 堆优化	最小生成树	O((n+m) log n)	O(n + m)	维护集合+优先队列
染色法	二分图判定	O(n + m)	O(n + m)	交替染色检测奇环
匈牙利	二分图最大匹配	O(n × e)	O(n + m + e)	增广路+递归让位

Kruskal 为什么是 O(m log m)？
① 排序 m 条边 → O(m log m)（瓶颈）
② 并查集操作 m 次 → O(m × α(n)) ≈ O(m)
③ 总计 O(m log m + m) = O(m log m)

T = O(m log m) + O(m·α(n)) = O(m log m)

因为 log m 增长远快于 α(n)，所以排序是主要瓶颈。

⚠️ 匈牙利算法注意事项：
① vis 数组必须在每轮 DFS 前重新清空，不是全局清一次
② match 数组存的是右部点 → 左部点的映射，不要搞反
③ 时间复杂度 O(n×e) 对于 n,m ≤ 500 的规模完全够用；更大规模需要用 Hopcroft-Karp O(e√n)

🎯 二分图的四个核心量
设二分图 G 有 n 个顶点、最大匹配数为 M。
① 最大匹配：最大的匹配边集大小 = M
② 最小点覆盖：选最少的顶点使每条边至少有一个端点被选
③ 最大独立集：选最多的顶点使任意两个都不相邻
④ 最小边覆盖：选最少的边使每个顶点至少关联一条被选边（无孤立点时）

🏆 König定理（CSP-S重要考点）

定理（König, 1931）：在二分图中，最小点覆盖 = 最大匹配。

完整四大量公式（对任意无孤立点的二分图）：

① 最大匹配 = M

② 最小点覆盖 = M = 最大匹配

③ 最大独立集 = n − M

④ 最小边覆盖 = n − M（无孤立点时）

记忆技巧：「点覆盖 + 独立集 = n」（互补），「最大匹配 = 最小点覆盖」（König）

📊 四大量关系总结

概念	含义	公式	与最大匹配的关系
最大匹配	最多的不相邻边	M	直接用匈牙利算法
最小点覆盖	最少的点覆盖所有边	= M	等于最大匹配（König定理）
最大独立集	最多的互不相邻点	= n − M	点覆盖的补集
最小边覆盖	最少的边覆盖所有点	= n − M	= 最大独立集（无孤立点）

💡 为什么CSP-S爱考？

📌 转化套路：题目描述的是「选最少的人/点/资源使得所有任务/边都被覆盖」→ 最小点覆盖 → 建二分图 → 求最大匹配。
题目描述「选最多的人/点使得互不冲突」→ 最大独立集 → n − 最大匹配。
关键：先识别出是二分图，再确定对应哪个量，最后套用公式。

⚓ 今日核心收获：二分图不只是「匹配」！通过 König 定理，匹配 → 点覆盖 → 独立集 → 边覆盖，一个算法解四个问题。

📌 模型一：棋盘/网格模型

套路：棋盘格子的相邻关系天然构成二分图（黑白染色 = 二分图两侧）。
• 放棋子问题：「放最多的棋子使得互不攻击」→ 最大独立集 = n − 最大匹配
• 多米诺骨牌：「用1×2骨牌覆盖棋盘」→ 最大匹配 = 骨牌数
• 识别方法：看到「网格」「相邻」「黑白交替」→ 先想二分图！

📌 模型二：任务分配 / 匹配模型

套路：「N个工人做N件工作，每人能做某些工作」→ 工人=左部，工作=右部，能做=连边 → 最大匹配
• 变体：「每头牛有偏好的牛栏」→ P1894 完美的牛栏
• 变体：「飞行员配对」→ P2756（经典匹配）
• 识别方法：看到「两类对象」+「配对/分配」→ 二分图匹配

📌 模型三：DAG最小路径覆盖

问题：给定 DAG，用最少的不相交路径覆盖所有顶点。
拆点转化：将每个顶点 u 拆成 u_出（左部）和 u_入（右部）。
DAG 中的边 u→v 变成左部 u_出到右部 v_入的二分图边。

最小路径覆盖数 = 顶点数 n − 拆点后二分图的最大匹配

为什么拆点有效？

每条路径中，一个顶点「入」连到下一个顶点「出」，相当于一次匹配。
匹配数 = 路径中「连接」的条数。路径数 = n − 连接数 = n − 匹配数。

经典例题：
• P2756 飞行员配对（本质就是DAG最小路径覆盖的拆点建图）
• LOJ #101 最小路径覆盖（模板）

📌 模型四：互斥/冲突模型 → 独立集

💡 套路：「某些元素不能同时选」→ 冲突关系建边 → 求最大独立集 = n − 最大匹配
前提：冲突关系必须构成二分图！先染色验证。
经典例题：「选最多的课程使得时间不冲突」→ 如果能二分染色 → 独立集

⚓ 建模四步法：① 识别两类对象 → ② 建二分图 → ③ 确定求哪个量（匹配/覆盖/独立集）→ ④ 套公式

📌 二分答案 + 二分图判定/匹配

核心套路：题目要求「最小化最大值」或「最大化最小值」→ 二分答案 → 用二分图判定或匹配验证。

经典例题 P1525 关押罪犯：
将 c 个罪犯分到两座监狱，罪犯间有仇恨值。最小化最大冲突。
→ 二分答案：二分最大冲突值 mid
→ 建图验证：只保留仇恨值 > mid 的边
→ 判定：该图是否为二分图？（染色法 O(n+m)）
→ 是二分图 → 可以分 → mid 可行 → 缩小；否则 → 增大

P1525 完整思路链：

① 二分冲突值 mid ∈ [0, max_w]
② 建图：罪犯为顶点，仇恨值 > mid 的罪犯对连边
③ 用染色法判定是否为二分图
④ 是二分图 → 两座监狱各放一侧 → 最大冲突 ≤ mid ✅
⑤ 总复杂度：O(log(max_w) × (n + m))

关键洞察：「能否分成两组使得组内无大冲突」= 二分图判定！

📊 CSP-S二分图考法全景

考法	核心算法	难度	代表题目
直接求最大匹配	匈牙利算法	普及+/提高−	P3386, P2756
二分图建模（匹配）	建图+匈牙利	普及+/提高−	P1894, P1640
二分图判定	染色法DFS/BFS	普及	P1330
二分答案+二分图	二分+染色判定	普及+/提高−	P1525
并查集+贪心（等价建模）	排序+并查集	普及+/提高−	P1525（另一种解法）
最小点覆盖/独立集	König定理转化	提高	棋盘覆盖类问题

⚡ 匈牙利算法优化技巧

🔧 时间戳优化（P1640技巧）：用 vis[v] = round 代替每轮 memset(vis, 0, ...)。
每轮DFS前 round++，判断 vis[v] == round 代替 vis[v] == true。
优化效果：避免 O(n) 的 memset，常数优化 3~5 倍，适用于 n 较大的场景。

Hopcroft-Karp 算法：O(e√n)，适合 n > 1000 的大规模二分图匹配。
CSP-S 中一般不需要，但了解其存在有助于判断数据规模。

⚠️ 常见错误总结：
① 忘记判断是否为二分图就直接做匹配 → 非二分图无König定理
② 建图方向搞反（左部和右部搞混）→ 匹配数可能不对
③ 多连通分量时只对一部分做染色/匹配 → 必须遍历所有未访问点
④ 混淆「点覆盖」和「边覆盖」→ 看清题目要求选的是点还是边

⚓ CSP-S实战策略：看到「两类对象配对」→ 二分图匹配；看到「能否分成两组」→ 二分图判定；看到「最小化最大值」→ 二分答案+判定/匹配

📊 Day05 全部算法复杂度对比

算法	解决的问题	时间复杂度	空间复杂度	核心思想
Kruskal	最小生成树	O(m log m)	O(n + m)	贪心选边+并查集判环
Prim 堆优化	最小生成树	O((n+m) log n)	O(n + m)	维护集合+优先队列
Prim 朴素	最小生成树（稠密图）	O(n²)	O(n²)	线性扫描最小边
染色法	二分图判定	O(n + m)	O(n + m)	交替染色检测奇环
匈牙利	二分图最大匹配	O(n × e)	O(n + m + e)	增广路+递归让位
König定理	最小点覆盖=最大匹配	O(n × e)	同匈牙利	匹配→点覆盖→独立集转化

复杂度数学证明汇总：

Kruskal：T = O(m log m)（排序瓶颈）+ O(m·α(n))（并查集）= O(m log m)
Prim 堆优化：T = O(m·log n)（堆操作）+ O(n·log n)（初始化）= O((n+m) log n)
染色法：T = Σ O(1)（节点访问）+ Σ O(deg(u))（边遍历）= O(n) + O(2m) = O(n + m)
匈牙利：T = n × O(m + e)（n轮DFS）= O(n·(m+e)) ≈ O(n·e)

MST算法：O(m log m) → O((n+m)log n) → O(n²)（稠密图优选Prim）

二分图：判定 O(n+m) → 匹配 O(n·e) → König定理四大量转化

🎯 选择策略速查

📍 稀疏图 MST → Kruskal
代码简单，并查集一搞。

📍 稠密图 MST → Prim
O(n²) 朴素版无堆操作。

📍 判断二分图 → 染色法
一遍 DFS/BFS 即可。

📍 二分图匹配 → 匈牙利
n,m ≤ 500 直接上。

📌 今日核心收获

🎯 Kruskal：贪心 + 排序 + 并查集 → 最小生成树最简实现
Prim：集合扩展 + 优先队列 → 稠密图 MST 最优解
MST性质：切割性质 + 环性质 → 边是否在MST中的判定
染色法：交替染色 + 奇环检测 → 二分图 O(n+m) 判定
匈牙利：增广路 + 递归让位 → 二分图最大匹配
König定理：最小点覆盖=最大匹配 → 四大量互相转化
二分图建模：棋盘/任务分配/DAG路径覆盖/独立集 → 识别+建图+套公式

🔑 全局易错点汇总：
Kruskal：① 边要排序 ② 并查集路径压缩+按秩合并 ③ 无向图重边取min
Prim：① 优先队列懒删除 ② 注意不连通图 ③ dist初始化为INF
染色法：① 不连通图要多次启动DFS ② 自环一定非二分图
匈牙利：① vis每轮DFS前清空 ② match是右→左映射 ③ 注意建图方向

📝 做题顺序建议
先完成知识点一的6道最小生成树题目巩固基础，再完成知识点二的6道二分图题目。
每道题先独立思考15分钟，再看题解。做完后对照检查清单复盘。

📚 知识点一：最小生成树

编号	题目	知识点	难度
1	P3366 【模板】最小生成树	Kruskal/Prim 模板	普及
2	P2330 [SCOI2005]繁忙的都市	MST 最大边最小	普及
3	P1194 买礼物	MST 变形（优惠建图）	普及
4	P1111 修复公路	Kruskal 应用（最早连通时间）	普及
5	P1546 [USACO3.1]最短网络 Agri-Net	Prim 经典题（邻接矩阵建图）	普及
6	P1991 [WC2005]卫星通讯	MST 第 k 大边	普及

📚 知识点二：二分图

编号	题目	知识点	难度
7	P1330 封锁阳光大学	染色法判定二分图	普及
8	P3386 【模板】二分图最大匹配	匈牙利算法模板	普及+/提高−
9	P2756 [USACO4.1]飞行员配对方案	二分图匹配	普及+/提高−
10	P1894 [USACO4.2]完美的牛栏	二分图匹配（建图建模）	普及+/提高−
11	P1640 [SCOI2010]连续攻击游戏	二分图匹配（时间戳优化）	普及+/提高−
12	P1525 [NOIP2010]关押罪犯	二分答案+二分图判定	普及+/提高−

📌 做题顺序建议（由易到难）：
最小生成树：P3366（模板）→ P2330 → P1194 → P1111 → P1546 → P1991
二分图：P1330（染色法）→ P3386（匈牙利模板）→ P2756 → P1894 → P1640 → P1525

每个知识点从模板题入手，再做变形应用。先保证模板题完全理解后再做其他题。

🔑 做题检查清单：
☐ Kruskal：边排序了吗？并查集初始化了吗？路径压缩+按秩合并？
☐ Prim：优先队列用的小根堆吗？dist 初始化为 INF？
☐ 染色法：不连通图多次启动 DFS？vis/color 每轮清空？
☐ 匈牙利：vis 每轮 DFS 前 memset？match 是右→左映射？
☐ 建图：无向图存了两遍边？重边取 min？自环处理了？

🏆

Day 05 完结

最小生成树与二分图 · MST & Bipartite Graph · 四大核心算法

📋 今日知识点回顾

✅ Kruskal 贪心选边 + 并查集判环 → O(m log m)
✅ Prim 维护集合 + 优先队列 → O((n+m)log n)
✅ MST性质：切割性质 + 环性质 → 边是否在MST中
✅ 染色法判定二分图 → 二分图 ⟺ 无奇环 → O(n+m)
✅ 匈牙利算法：增广路 + 递归让位 → 二分图最大匹配 O(n·e)
✅ König定理：最小点覆盖=最大匹配 → 四大量转化
✅ 二分图建模：棋盘/任务分配/DAG路径覆盖/独立集
✅ 完整代码模板 + 洛谷例题 + CSP-S考法分析

算法+性质+建模全覆盖，Day 06 继续挑战更复杂的图论问题！🚀

✏️

🌳 Kruskal算法 — 问题引入与贪心证明

🌳 Kruskal — 并查集深入图解

🌳 Kruskal — 完整例题SVG模拟 + 代码

🌳 Kruskal — 复杂度数学推导

🔍 Prim算法 — 与Dijkstra对比 + 实现

🔍 Prim — SVG逐步模拟执行

🔍 Prim — 复杂度数学推导

🌳 MST性质与CSP-S建模专题

🎨 二分图判定 — 什么是二分图？

🎨 染色法判定二分图 — 代码实现

🎨 染色法 — 复杂度分析与例题

💕 二分图最大匹配 — 匈牙利算法

💕 匈牙利算法 — 代码实现

💕 匈牙利算法 — 复杂度与算法对比

💕 König定理 — 二分图四大量关系

💕 二分图建模专题 — CSP-S常见套路

💕 二分图进阶 — 二分答案与CSP-S考法

📊 Day 05 知识总结 + 算法全景对比

📋 Day 05 题单