自动接线器 题解¶
解法贡献：Codex（GPT-6）整理了最大匹配到最小点覆盖的构造证明，重写 Hopcroft–Karp 的显式栈实现，并补全多解评测器。使用的是已有的二分图匹配与点覆盖方法。
解法比较¶
标程采用 Hopcroft–Karp。它为每条关系保存一个邻接目标，另存匹配数组；显式单位流还需保存关系边、源汇边的正反残量边与容量。两者渐进界相同，专用匹配表示减少了边记录的存储。
出题人解法把可选端点分为左右两部，建立源到左部、左到右、右到汇的单位容量网络，用 Dinic 求最大匹配，再由交替可达性构造最小点覆盖。匹配边不能共享端点，单位流与匹配一一对应；由未匹配左点出发，按非匹配边向右、匹配边向左搜索，所得 \((L\setminus Z_L)\cup Z_R\) 是与最大匹配同大的覆盖，证明见下文。
构造覆盖时必须从未匹配左点出发，并按非匹配边向右、匹配边向左搜索；若从右侧出发，则必须同时反转规则和可遍历的邻接方向。Codex（GPT-6）的实现采用 Hopcroft–Karp 的分层增广和显式栈。设总点数为 \(V\) 、关系数为 \(E\) ，单位匹配网络的 Dinic 与 Hopcroft–Karp 均有 \(O((V+E)\sqrt V)\) 时间界，空间为 \(O(V+E)\) .
二分图点覆盖¶
工作台端口构成左部 \(U\) ，电脑端口构成右部 \(W\) . 每条线路都是跨越两部的一条边。要找的集合正是最小点覆盖：每条边至少有一个端点被选。
设最大匹配为 \(M\) . 匹配中的边两两没有公共端点，所以任意点覆盖至少要选 \(\lvert M\rvert\) 个点。接下来构造一个恰有这么多点的覆盖，便能同时证明最优性。
找到最大匹配¶
使用 Hopcroft–Karp 算法。每轮从所有未匹配的左部点开始 BFS，对交错路径分层；再沿层次寻找一批互不相交的最短增广路，同时增广。增广路上的边在“非匹配边”和“匹配边”之间交替，翻转后匹配数增加一。
参考程序只给左部点保存层数，经过右部点的匹配边后到达下一层左部点。DFS 用显式栈记录左部点，找到未匹配右端点后，从栈顶向栈底依次翻转匹配。当前弧和失败标记避免一轮内反复扫描已失败的分支。分层时必须限制在最短增广路的层数。
由交错可达性构造点覆盖¶
匹配最大后，从所有未匹配的左部点出发，沿以下方向搜索：
- 左部到右部：只走非匹配边。
- 右部到左部：只走匹配边。
记到达的左、右部点分别为 \(Z_U,Z_W\) . 输出
覆盖性。 若一条边的左端点不在 \(Z_U\) ，已经被选。若左端点在 \(Z_U\) ，则该边的右端点也在 \(Z_W\) ：非匹配边可以直接搜索到，匹配边的右端点则是进入这个已匹配左端点的前驱。故每条边都有端点被选。
大小。 搜索不可能到达未匹配的右部点，否则存在增广路，与最大匹配矛盾。所有未匹配的左部点都属于 \(Z_U\) ，因此两侧未匹配点都不会入选。每条匹配边的两个端点要么都可达，要么都不可达，于是恰好选其中一个。最终 \(\lvert S\rvert=\lvert M\rvert\) ，达到前述下界。
搜索必须从未匹配的左部点开始，并与边的搜索方向一致。仅输出某一侧所有已匹配点不一定覆盖全部边，例如一个工作台连接多个电脑的星形图。
复杂度与评测¶
时间为 \(O((n+m)\sqrt n)\) ，空间为 \(O(n+m)\) . 孤立点不会影响匹配或覆盖；重复线路不会改变最优数量，实现仍能处理。
tests/checker.py 接收输入、标准答案和选手输出三个文件路径。它独立检查整数格式、端口范围、重复编号、声明数量、最优数量和所有边的覆盖。标准答案只提供最优数量，不要求选择相同端口。
小图检查穷举全部非空的 \(3\times3\) 二分图，并直接枚举所有端口子集求最优覆盖；另有随机含重边的图。性能测量见评测环境与性能。