图论算法实战：点双连通分量、拓扑排序与同余最短路解析
矿场搭建与点双连通分量
在矿场搭建问题中，我们需要将矿井抽象为无向图，并分析其点双连通分量（VDCC）以确保在任意一个节点坍塌时，其余节点仍能通过出口逃生。核心逻辑基于割点的数量进行分类讨论：
- 若一个连通块内没有割点，说明任意两点间至少有两条独立路径。此时至少需要建立 2 个出口，方案数为 $C(n, 2)$。
- 若连通块内仅有 1 个割点，必须在非割点区域建立 1 个出口。若割点坍塌，该区域仍可通过此出口逃生，方案数为 $n - 1$。
- 若连通块内包含 2 个或更多割点，则无需额外建立出口。因为即使某个割点坍塌，剩余节点仍可通过其他割点到达相邻的连通块并逃生，方案数为 1。
最终的最小出口总数为各连通块所需出口数之和，总方案数为各连通块方案数之积。以下是优化后的 Tarjan 算法实现，通过一次 DFS 同步求出割点与点双连通分量：
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN], timer;
bool is_cut[MAXN];
stack<int> stk;
long long total_ways = 1;
int min_exits = 0;
int node_count = 0;
void tarjan(int u, int parent) {
dfn[u] = low[u] = ++timer;
stk.push(u);
node_count++;
int child_count = 0;
for (int v : adj[u]) {
if (!dfn[v]) {
child_count++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
// 发现点双连通分量
if (low[v] >= dfn[u]) {
if (parent != -1) is_cut[u] = true;
int cut_count = 0;
int vdcc_size = 0;
int node;
do {
node = stk.top();
stk.pop();
vdcc_size++;
if (is_cut[node]) cut_count++;
} while (node != v);
vdcc_size++; // 加上当前节点 u
if (is_cut[u]) cut_count++;
if (cut_count == 0) {
min_exits += 2;
total_ways *= (long long)vdcc_size * (vdcc_size - 1) / 2;
} else if (cut_count == 1) {
min_exits += 1;
total_ways *= (vdcc_size - 1);
}
}
} else if (v != parent) {
low[u] = min(low[u], dfn[v]);
}
}
if (parent == -1 && child_count >= 2) {
is_cut[u] = true;
}
}
void solve_case(int case_id, int m) {
for (int i = 0; i < MAXN; i++) {
adj[i].clear();
dfn[i] = low[i] = is_cut[i] = 0;
}
timer = 0;
node_count = 0;
min_exits = 0;
total_ways = 1;
while (!stk.empty()) stk.pop();
int max_node = 0;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
max_node = max({max_node, u, v});
}
for (int i = 1; i <= max_node; i++) {
if (!dfn[i]) {
node_count = 0;
tarjan(i, -1);
}
}
cout << "Case " << case_id << ": " << min_exits << " " << total_ways << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m, case_id = 1;
while (cin >> m && m) {
solve_case(case_id++, m);
}
return 0;
}
协处理器调度与拓扑排序
在存在任务依赖关系的有向无环图（DAG）中，我们需要合理调度主处理器和协处理器（副处理器）的任务。为了最小化协处理器的调用批次，应当采用贪心策略：优先执行所有当前入度为 0 的主处理器任务。只有当主处理器队列为空时，才将当前入度为 0 的协处理器任务作为一个批次执行，并将批次计数器加一。
该过程可以通过维护两个独立的队列来实现拓扑排序，确保主任务始终优先消耗：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<int> type(n + 1);
for (int i = 1; i <= n; i++) {
cin >> type[i];
}
vector<vector<int>> graph(n + 1);
vector<int> in_degree(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u++; v++; // 转换为 1-based 索引
graph[u].push_back(v);
in_degree[v]++;
}
queue<int> q_main, q_coproc;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
if (type[i] == 0) q_main.push(i);
else q_coproc.push(i);
}
}
int coproc_batches = 0;
while (!q_main.empty() || !q_coproc.empty()) {
// 优先清空主处理器队列
while (!q_main.empty()) {
int u = q_main.front();
q_main.pop();
for (int v : graph[u]) {
if (--in_degree[v] == 0) {
if (type[v] == 0) q_main.push(v);
else q_coproc.push(v);
}
}
}
// 主处理器空闲时，处理协处理器任务
if (!q_coproc.empty()) {
coproc_batches++;
while (!q_coproc.empty()) {
int u = q_coproc.front();
q_coproc.pop();
for (int v : graph[u]) {
if (--in_degree[v] == 0) {
if (type[v] == 0) q_main.push(v);
else q_coproc.push(v);
}
}
}
}
}
cout << coproc_batches << "\n";
return 0;
}
跳楼机与同余最短路
当面临通过若干种固定步长（如 $x, y, z$）组合到达目标楼层的问题时，可以使用同余最短路算法。其核心思想是选取最小的步长（假设为 $x$）作为模数，定义状态 $dist[i]$ 表示通过步长 $y$ 和 $z$ 能够到达的、模 $x$ 余 $i$ 的最小楼层高度。
状态转移方程为：从楼层 $u$ 可以通过步长 $y$ 到达 $(u + y) \pmod x$，边权为 $y$；同理可通过步长 $z$ 到达 $(u + z) \pmod x$，边权为 $z$。构建出包含 $x$ 个节点的有向图后，使用 Dijkstra 算法求解单源最短路。最终，对于每个余数 $i$，若 $dist[i] \le H$（目标最大楼层），则它对总方案的贡献为 $\lfloor \frac{H - dist[i]}{x} \rfloor + 1$。
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const ll INF = 1e18;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll H;
int x, y, z;
if (!(cin >> H >> x >> y >> z)) return 0;
// 确保 x 是最小的步长，以优化图的大小
if (x > y) swap(x, y);
if (x > z) swap(x, z);
if (x == 1) {
cout << H << "\n";
return 0;
}
vector<vector<pair<int, int>>> adj(x);
for (int i = 0; i < x; i++) {
adj[i].push_back({(i + y) % x, y});
adj[i].push_back({(i + z) % x, z});
}
vector<ll> dist(x, INF);
priority_queue<pli, vector<pli>, greater<pli>> pq;
dist[1 % x] = 1; // 初始在第 1 层
pq.push({1, 1 % x});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
ll weight = edge.second;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
ll total_floors = 0;
for (int i = 0; i < x; i++) {
if (dist[i] <= H) {
total_floors += (H - dist[i]) / x + 1;
}
}
cout << total_floors << "\n";
return 0;
}
