2026-09-06 秋招XX笔试复盘
题目一：传送门最短路
题目大意
给定一张无向图，允许自环和重边。普通边 (u,v,w) 双向通行，代价为 w；传送门 (u,v) 也双向通行，代价为 0。
从 st 到 ed，最多使用 k 次传送门，k≤10，并且不能连续使用两次传送门。用过一次后，要先走一条普通边才能再用。起点可以直接使用传送门，也可以全程不用。求最小总代价。
思路分析
只记录“到了哪个点”不够。即使在同一个点，已经用了几次传送门、上一步是不是传送门，都会影响下一步能怎么走。
把状态写成 (u,c,last)：u 是当前点，c 是已用次数，last 表示上一步是否使用传送门。转移只有两类：
- 走普通边：
(u,c,last) → (v,c,0)，增加边权w。 - 使用传送门：只有
last=0且c<k时可以走，转到(v,c+1,1)，代价不变。
起点是 (st,0,0)，所以一开始就能用传送门。到终点后，不论 last 是什么都能结束，不必再补一条普通边。
我当时想的 2k+1 层图和这个状态等价。偶数层 2c 表示用了 c 次、可以再用；奇数层 2c+1 表示刚用了第 c+1 次。普通边既要能在偶数层内移动，也要能从奇数层走到下一偶数层；传送门只从偶数层走到下一奇数层。每条无向边对应的两个方向都要处理。
普通边权非负时，在这些状态上跑 Dijkstra。设普通边数为 m、传送门数为 p，状态数为 O(n(k+1))，转移数为 O((m+p)(k+1))。用堆的时间复杂度为 O((n+m+p)(k+1) log(n(k+1)))；不显式复制所有层，额外空间为 O(n(k+1)+m+p)。
参考代码
普通边权非负，距离使用 long long，不可达时返回 -1。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 点编号 1..n；normal 和 portal 都已按无向边存好。
// 普通边权非负，有限最短距离须小于 LLONG_MAX；不可达返回 -1。
ll shortest_path(int n, int k, int st, int ed,
const vector<vector<pair<int, ll>>>& normal,
const vector<vector<int>>& portal) {
const ll INF = LLONG_MAX;
vector<vector<vector<ll>>> dist(
k + 1, vector<vector<ll>>(2, vector<ll>(n + 1, INF)));
// (距离, 节点, 已用传送门次数, 上一步是否为传送门)
using State = tuple<ll, int, int, int>;
priority_queue<State, vector<State>, greater<State>> pq;
dist[0][0][st] = 0;
pq.emplace(0, st, 0, 0);
while (!pq.empty()) {
auto [d, u, used, last] = pq.top();
pq.pop();
if (d != dist[used][last][u]) continue;
if (u == ed) return d;
auto relax = [&](int v, int next_used, int next_last, ll w) {
if (w > INF - d) return;
ll nd = d + w;
if (nd < dist[next_used][next_last][v]) {
dist[next_used][next_last][v] = nd;
pq.emplace(nd, v, next_used, next_last);
}
};
for (auto [v, w] : normal[u]) relax(v, used, 0, w);
if (!last && used < k)
for (int v : portal[u]) relax(v, used + 1, 1, 0);
}
return -1;
}第四题：Alice／Bob赛马
题目大意
Alice 和 Bob 各有 n 匹马。给出一个 n×n 矩阵，a[i][j]=1 表示 Alice 的第 i 匹马能赢 Bob 的第 j 匹马，-1 表示会输。
每轮 Bob 先出一匹马，Alice 再选一匹应战，两匹马随后移出，直到全部用完。双方都按最优策略行动：Bob 想让 Alice 的分数尽可能低，Alice 想让自己的分数尽可能高。
先求 Alice 能保证的胜场数；若赢 +1、输 -1，再换算为总分。
思路分析
我当时把它理解成给马分配对手，类比“球放到能放的洞里，最多能放多少个”。沿着这个想法，把所有 a[i][j]=1 连成二分图边：左边是 Alice 的马，右边是 Bob 的马。设最大匹配大小为 M。
先看上界。每匹马只能用一次，所以 Alice 最后赢下的那些对局本身就是一个匹配，胜场数不可能超过 M。
再看下界。Bob 可以根据前面几轮动态选马，不能假设他提前公布完整顺序。不过 Alice 仍然能保证 M 场：看当前剩余图的一个最大匹配。
- Bob 出的马在匹配里，就用它匹配到的 Alice 马应战。这轮赢 1 场，删除两匹马后，剩余匹配至少还有
M-1条。 - Bob 出的马不在匹配里，Alice 也选一匹不在匹配里的马。两边剩余马数相同，所以这样的 Alice 马一定存在。删除这两个未匹配点，原来的
M条匹配都还在。
每轮都能保持“已赢场数＋剩余最大匹配大小”至少为最初的 M。因此不论 Bob 怎么出，Alice 都能保证 M 场，和上界合起来就是答案。
只统计胜场时输出 M。若赢 +1、输 -1，总分为 M-(n-M)=2M-n。
下面用增广路求二分图最大匹配，稠密矩阵下时间复杂度 O(n³)，额外空间 O(n)。规模较大时可以换 Hopcroft–Karp，复杂度为 O(E√n)。
参考代码
函数返回最大胜场数，计分换算按题目实际定义处理。
#include <bits/stdc++.h>
using namespace std;
int maximum_wins(const vector<vector<int>>& a) {
int n = a.size();
vector<int> match(n, -1), seen(n);
function<bool(int)> augment = [&](int i) {
for (int j = 0; j < n; ++j) {
if (a[i][j] != 1 || seen[j]) continue;
seen[j] = 1;
if (match[j] == -1 || augment(match[j])) {
match[j] = i;
return true;
}
}
return false;
};
int wins = 0;
for (int i = 0; i < n; ++i) {
fill(seen.begin(), seen.end(), 0);
if (augment(i)) ++wins;
}
return wins;
}