先求最大匹配,再在按匹配边定向的交错图上用强连通分量与自由点可达性判定每条边是否属于某个大小为 n 的匹配。
OJ: roj
题目 ID: 1730
难度:提高+/省选-
标签:二分图匹配Hopcroft-Karp强连通分量python
创建: 2026-10-07 19:03
更新: 2026-10-07 19:03
形式化题目
给定一个二分图
输出一个 1;否则为 0。也就是说输出是判定结果的取反:0 才表示"这条边可用"。
约束:
注意
正解
思路
先排除无解情形。 如果最大匹配的大小 1。这一步用 Hopcroft-Karp 在
难点在第二步:有了一个匹配,怎么判断别的边。 朴素的"逐条边删掉再求一次最大匹配"是
关键观察是交错路/交错环的翻转:若
- 若
同时属于某个交错环 (在 上把匹配与非匹配边互换,得到的新匹配大小不变,仍饱和左部),则 可用; - 若
位于某条从右部自由点出发的交错路上,则沿这条路径翻转前缀(或整条路径)也能把 变成匹配边,且匹配大小不变,仍饱和左部。
这两条覆盖了全部情形,也正是经典的"边属于某个最大匹配"判定的两条判据。
把这两条判据变成图上可达性。 按
- 条件 (a):
与 在 的同一个强连通分量里 该边落在一条交错环上。用 Tarjan(或 Kosaraju)一次求出所有 SCC。 - 条件 (b):
在 中从某个 未匹配的右部点可达。把所有右部自由点作为源做一次 BFS/DFS 即可。
匹配边本身当然属于 0。
用样例 1 直观感受一下
flowchart LR
subgraph S["同一个强连通分量(两条交错环共用 L1)"]
L1["左 1"] --> R2["右 2"]
R2 --> L3["左 3"]
L3 --> R4["右 4"]
R4 --> L1
R2 --> L4["左 4"]
L4 --> R3["右 3"]
R3 --> L1
R4 --> L4
end
L2["左 2"] --> R1["右 1"]
R1 --> L1
R1 --> L3
R1 --> L4
逐条对照期望输出 1000 / 0111 / 1000 / 1000(第 1 行):0;非匹配边 0;非匹配边 1。
(实际
为什么结论与
实现要点:
- 最大匹配用 Hopcroft-Karp,
。 - 有向图
的弧数恰好等于原图边数(每条边转成一条弧),上界 ,链式前向星开 460005足够。 的顶点数只有 ,Tarjan 用递归也不会爆栈。 - 输出时先全部填
1,再把"可用"的边改写成0;这样非边自动是1,不需要单独处理。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 19:03
# update_at: 2026-10-07 19:03
import sys
from collections import deque
INF = 10 ** 9 # 分层 BFS 里"不可达"的层号,比任何真实层号都大
UNMATCHED = -1 # 匹配数组里的"该点未匹配",左、右部共用同一个哨兵
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[list[int]] # 邻接表:顶点自己编号,表中存邻居编号
type Table = list[bytearray] # 答案表:每行一个字节串,'0' 表示这条边可用
def max_matching(adj: Adj, n: int, m: int) -> tuple[list[int], list[int]]:
"""Hopcroft-Karp:返回 (左部匹配数组, 右部匹配数组) 表示的一个最大匹配。"""
match_l = [UNMATCHED] * n
match_r = [UNMATCHED] * m
dist = [0] * n # 分层 BFS 中左部点的层号,只对左部点有意义
def build_layers() -> bool:
"""按未匹配的左部点重新分层,返回本轮是否还存在增广路。"""
que = deque(u for u in range(n) if match_l[u] == UNMATCHED)
for u in range(n):
dist[u] = 0 if match_l[u] == UNMATCHED else INF
found = False
while que:
u = que.popleft()
for v in adj[u]:
w = match_r[v]
if w == UNMATCHED:
found = True # 走到未匹配的右部点,就有增广路
elif dist[w] == INF:
dist[w] = dist[u] + 1 # 沿匹配边继续往下分层
que.append(w)
return found
def augment(u: int) -> bool:
"""只在分层图上从 u 找一条增广路并翻转沿途匹配。"""
for v in adj[u]:
w = match_r[v]
# v 未匹配(增广路到头),或 v 的匹配对象恰在下一层且它还能继续增广
can_extend = w == UNMATCHED or (dist[w] == dist[u] + 1 and augment(w))
if can_extend:
match_l[u] = v
match_r[v] = u
return True
dist[u] = INF # 本轮 u 已确认增广失败,后面不再重复搜索
return False
while build_layers():
for u in range(n):
if match_l[u] == UNMATCHED:
augment(u)
return match_l, match_r
def scc_ids(adj: Adj, total: int) -> list[int]:
"""迭代版 Tarjan,返回每个顶点所属的强连通分量编号。"""
dfn = [0] * total
low = [0] * total
comp = [0] * total
on_stack = [False] * total
nxt = [0] * total # 每个顶点下一次要处理的出弧下标
stack: list[int] = [] # Tarjan 维护的栈
call: list[int] = [] # 手工模拟递归用的调用栈
timer = 0
count = 0
for root in range(total):
if dfn[root]:
continue
timer += 1
dfn[root] = low[root] = timer
stack.append(root)
on_stack[root] = True
call.append(root)
while call:
u = call[-1]
if nxt[u] < len(adj[u]):
v = adj[u][nxt[u]]
nxt[u] += 1
if dfn[v] == 0:
timer += 1
dfn[v] = low[v] = timer
stack.append(v)
on_stack[v] = True
call.append(v)
elif on_stack[v]: # 指向栈内已访问点,用 dfn 更新 low
low[u] = min(low[u], dfn[v])
else:
call.pop()
if low[u] == dfn[u]:
while True:
w = stack.pop()
on_stack[w] = False
comp[w] = count
if w == u:
break
count += 1
if call: # 回溯到父亲,把儿子的 low 传上去
parent = call[-1]
low[parent] = min(low[parent], low[u])
return comp
def saturated_edges(adj: Adj, match_l: list[int], match_r: list[int], n: int, m: int) -> Table:
"""已知存在大小为 n 的匹配时,逐条边判定它能否入选:可入选填 '0',否则保持 '1'。"""
ans = [bytearray(b'1' * m) for _ in range(n)]
# 按匹配 M 定向的交错有向图 D:左部点编号 0..n-1,右部点编号 n..n+m-1
total = n + m
dag: Adj = [[] for _ in range(total)]
for u in range(n):
for v in adj[u]:
if match_l[u] == v:
dag[u].append(n + v) # 匹配边:左 -> 右
else:
dag[n + v].append(u) # 非匹配边:右 -> 左
comp = scc_ids(dag, total)
# 从所有未被 M 匹配的右部点出发,标出 D 上可达的顶点
reachable = bytearray(total)
que = deque()
for v in range(m):
if match_r[v] == UNMATCHED:
reachable[n + v] = 1
que.append(n + v)
while que:
x = que.popleft()
for y in dag[x]:
if not reachable[y]:
reachable[y] = 1
que.append(y)
for u in range(n):
row = ans[u]
for v in adj[u]:
in_cycle = comp[u] == comp[n + v] # 条件 (a):这条边落在一条交错环上
via_free = reachable[n + v] == 1 # 条件 (b):交错路前缀可翻转到这条边
if match_l[u] == v or in_cycle or via_free:
row[v] = 48 # 48 == ord('0'),属于某个大小为 n 的匹配
return ans
def edge_table(adj: Adj, n: int, m: int) -> Table:
"""整题的答案表:无解(左部无法全匹配)时全填 '1',否则交给逐边判定。"""
match_l, match_r = max_matching(adj, n, m)
has_full = all(x != UNMATCHED for x in match_l) # 左部全被匹配才存在大小为 n 的匹配
if not has_full:
return [bytearray(b'1' * m) for _ in range(n)]
return saturated_edges(adj, match_l, match_r, n, m)
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n = int(next(data))
m = int(next(data)) # 题面保证 n <= m,算法本身不需要这个条件
rows = [next(data).decode() for _ in range(n)]
adj = [[j for j, ch in enumerate(row) if ch == '1'] for row in rows]
ans = edge_table(adj, n, m)
sys.stdout.write('\n'.join(row.decode() for row in ans) + '\n')
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 19:03
* update_at: 2026-10-07 19:03
*/
// 一本通 1730《二分图》:判定每条边是否属于某个「饱和左部」的匹配(题面保证 n <= m)。
// 1. Hopcroft-Karp 求最大匹配;若匹配数不足 n,则不存在大小为 n 的匹配,全部输出 1。
// 2. 取定一个最大匹配 M,按 M 建交错有向图 D(左部点 1..n,右部点 n+1..n+m):
// 匹配边 u-v 建成弧 u -> v,非匹配边 u-v 建成弧 v -> u。
// 3. 非匹配边 (u,v) 属于某个大小为 n 的匹配,当且仅当
// (a) u 与 v 在 D 的同一个强连通分量里(该边落在一条交错环上),或
// (b) v 能从某个「M 未匹配的右部点」沿 D 走到(该边落在一条交错路上,翻转前缀即可)。
// 匹配边本身恒属于。
// 4. 输出取反:属于输出 0,否则(含非边)输出 1。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 305; // 左部点数上限
const int MAXM = 1505; // 右部点数上限
const int MAXV = MAXN + MAXM;
const int MAXE = 460005; // 有向弧上限:n * m = 300 * 1500 = 450000
const int INF = 0x3f3f3f3f;
int n, m; // 左部 n 个点、右部 m 个点(保证 n <= m)
vector<int> g[MAXN]; // g[u] = 左部点 u 的全部右部邻居
int matchL[MAXN]; // matchL[u] = 左部点 u 匹配到的右部点,0 表示未匹配
int matchR[MAXM]; // matchR[v] = 右部点 v 匹配到的左部点,0 表示未匹配
int distL[MAXN]; // 分层 BFS 中左部点 u 的层号,INF 表示本轮不可达
// 链式前向星存交错有向图 D
int head[MAXV]; // head[x] = 顶点 x 的第一条出弧编号
struct Edge {
int to; // 弧的终点
int ne; // 同起点的下一条弧
};
Edge ed[MAXE];
int edge_cnt;
int dfn[MAXV], low[MAXV]; // Tarjan 的时间戳与回溯值
int stk[MAXV], stk_top; // Tarjan 的栈
bool in_stk[MAXV]; // 顶点是否还在栈中
int scc_id[MAXV], scc_cnt; // 每个顶点所属的强连通分量编号
int timer;
bool reachable[MAXV]; // 从「M 未匹配的右部点」出发在 D 上可达
char ans[MAXN][MAXM]; // 答案矩阵:1 表示该边不属于任何大小为 n 的匹配
char line[MAXM]; // 读入一行的缓冲
// 往交错有向图 D 里加一条弧 u -> v
void add_edge(int u, int v) {
edge_cnt++;
ed[edge_cnt].to = v;
ed[edge_cnt].ne = head[u];
head[u] = edge_cnt;
}
// Hopcroft-Karp 的分层:未匹配的左部点为第 0 层,返回本轮是否存在增广路
bool hk_bfs() {
queue<int> que;
for (int u = 1; u <= n; u++) {
if (matchL[u] == 0) {
distL[u] = 0;
que.push(u);
} else {
distL[u] = INF;
}
}
bool found = false;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int v : g[u]) {
int w = matchR[v];
if (w == 0) {
found = true; // 存在一条长度更短或同长的增广路
} else if (distL[w] == INF) {
distL[w] = distL[u] + 1; // 沿匹配边继续分层
que.push(w);
}
}
}
return found;
}
// 沿分层图找一条增广路并翻转匹配
bool hk_dfs(int u) {
for (int v : g[u]) {
int w = matchR[v];
if (w == 0 || (distL[w] == distL[u] + 1 && hk_dfs(w))) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
distL[u] = INF; // 本轮 u 已确认失败,避免重复搜索
return false;
}
// 返回最大匹配的边数
int hopcroft_karp() {
int cnt = 0;
while (hk_bfs()) {
for (int u = 1; u <= n; u++) {
if (matchL[u] == 0 && hk_dfs(u)) cnt++;
}
}
return cnt;
}
// Tarjan 求强连通分量(D 的顶点数不超过 1800,递归深度安全)
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
stk[++stk_top] = u;
in_stk[u] = true;
for (int e = head[u]; e; e = ed[e].ne) {
int v = ed[e].to;
if (dfn[v] == 0) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
scc_cnt++;
int w;
do {
w = stk[stk_top--];
in_stk[w] = false;
scc_id[w] = scc_cnt;
} while (w != u);
}
}
// 从所有「M 未匹配的右部点」出发做 BFS,标出 D 上能到达的顶点
void bfs_from_free_right() {
queue<int> que;
for (int v = 1; v <= m; v++) {
if (matchR[v] == 0) {
reachable[n + v] = true;
que.push(n + v);
}
}
while (!que.empty()) {
int x = que.front();
que.pop();
for (int e = head[x]; e; e = ed[e].ne) {
int y = ed[e].to;
if (!reachable[y]) {
reachable[y] = true;
que.push(y);
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", line + 1);
for (int j = 1; j <= m; j++) {
if (line[j] == '1') g[i].push_back(j);
}
}
int matched = hopcroft_karp();
// 默认全部输出 1:非边,以及不属于任何大小为 n 的匹配的边
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) ans[i][j] = '1';
ans[i][m + 1] = '\0';
}
if (matched < n) {
for (int i = 1; i <= n; i++) puts(ans[i] + 1);
return 0;
}
// 按匹配 M 建交错有向图 D
for (int u = 1; u <= n; u++) {
for (int v : g[u]) {
if (matchL[u] == v) add_edge(u, n + v); // 匹配边:左 -> 右
else add_edge(n + v, u); // 非匹配边:右 -> 左
}
}
for (int x = 1; x <= n + m; x++) {
if (dfn[x] == 0) tarjan(x);
}
bfs_from_free_right();
for (int u = 1; u <= n; u++) {
for (int v : g[u]) {
if (matchL[u] == v) ans[u][v] = '0'; // 匹配边恒属于
else if (scc_id[u] == scc_id[n + v]) ans[u][v] = '0'; // 条件 (a):交错环
else if (reachable[n + v]) ans[u][v] = '0'; // 条件 (b):交错路
}
}
for (int i = 1; i <= n; i++) puts(ans[i] + 1);
return 0;
}复杂度
设
总结
本题的模型是"每条边是否属于某个最大匹配",经典结论是两条判据的并集:同强连通分量(交错环)或右端点从自由右部点可达(交错路)。把这两条落成"按匹配边定向 + Tarjan + 一次 BFS",整道题就是 Hopcroft-Karp 加两个线性图论模板的拼接。
三个容易踩的坑:一是 1,不能继续走后面的判定;三是输出取反——题面要求"不存在这样的匹配才输出 1",写代码时用"先全填 1 再改 0"最不容易错。
关于数据:本题的 data/ 由随题目附带的 data.py 生成(10 个点,含题面 3 个样例与若干随机/顶格点),题面文字也属于网络重建,因此数据并非官方原始测试数据,只是按题面约束构造的自造数据。本仓库的 std.cpp 与本解法思路一致(同样的 Hopcroft-Karp + SCC + 自由点可达),已在全部 10 个点上与 main.cpp 的实跑结果比对一致。