题解：P5049 [NOIP 2018 提高组] 旅行加强版

此处提供一种思路较为简单，统一处理所有可能情况的非递归图遍历模拟+贪心解法。

对题中所给的图的邻接表排序后，如果该图是一颗无根树，直接深度优先遍历便可获得答案。如果该图比无根树多一条边，则先用 Tarjan 算法或直接 DFS 标记环上的所有节点。对环外的所有节点，沿用无根树的解法，以保证每个点均访问到；对环内的所有节点

i

，由于允许切断环上的一条边，如果之前未跳过节点，且即将访问的邻接节点

j

也在环上的话，我们基于以下这种统一的策略决定是否跳过

j

：

如果跳过 $j$ 后，存在下一即将访问的节点 $k$ （且之前未被访问过），且 $k < j$ ，则跳过
否则不跳过

考虑基于访问栈实现的非递归图遍历算法，约定栈顶的元素为当前即将访问的节点

i

，访问

i

后，根据前序遍历算法计算下一可访问节点

j

。如果

j

不存在，算法结束。如果

j

存在，当前尚未拆环，且

j

的父节点

p

和

j

均在环上，则尝试拆除

p \to j

边：将

j

弹出并计算下一可访问节点

k

，如果

k

不存在，则将

j

压回栈内；如果

k

存在且

k < j

，我们贪心地跳过

j

，将

j

标记为未访问，访问

k

并继续迭代；如果

k

存在且

k > j

，则不应在此拆环，此时将错误压栈的

k

弹出，并压入

j

，然后将

k

加入

j

邻接表的最后，恢复原有的访问顺序，访问

j

并继续迭代。

如果不注意上述算法可能改变被访问节点的父节点，直接根据访问栈确定父节点，则只能得到 88 分。正确的处理策略是：对于被加入

j

邻接表的

k

节点，我们先保留其原有的父节点，除非在访问这条新增的

j \to k

边（不包含图中可能原有的

j \to k

边）前，算法通过图中原有的其他边访问到

k

节点时，更新

k

的父节点，否则该父节点保持不变。以上方才完全撤销了迭代遍历算法中包含的所有可能对答案产生影响的副作用。

该算法虽思路较为简单，但撤销错误访问时引入的重排操作可能带来约

\times 2

的常数开销，故性能不如无副作用预测

k

的思路较为复杂的其他算法。

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// 本题输入
int n, m;
vector<vector<int>> neigh;  // 输入后对每个数组升序排序

// 无根树特解
void solve_tree(int i, int p = -1)
{
  cout << i + 1 << ' ';
  for(int j : neigh[i]) {
    if(j == p) continue;
    solve_tree(j, i);
  }
}

// tarjan 算法变量
vector<int> dfn, low, loop;
stack<int> stk;

// tarjan 边双连通算法找环
void tarjan(int i, int p = -1)
{
  stk.push(i);
  static int seq;
  dfn[i] = low[i] = seq++;

  for(int j : neigh[i]) {
    if(j == p) continue;
    if(dfn[j] < 0) {
      tarjan(j, i);
      low[i] = min(low[i], low[j]);
    } else {
      low[i] = min(low[i], dfn[j]);
    }
  }
  if(dfn[i] != low[i]) return;
  if(stk.top() == i) return stk.pop();  // 单点非环

  for(;;) {  // 多点成环，进入 loop 数组的顺序为搜索序的逆序
    int j = stk.top();
    stk.pop();
    loop.push_back(j);
    if(j == i) break;
  }
}

// 迭代遍历算法变量
vector<bool> looped;   // 每个点是否在环上
vector<int> idx, par;  // 每个点的遍历进度和父节点编号，初始时均为 -1
vector<int> parfix;  // i -> 父节点不是 i 的第一个“子节点”在 neigh[i] 中的下标，初始化为越界值 n

// 可干预非递归图遍历算法
bool next()
{
  while(!stk.empty()) {
    int i = stk.top();
    while(idx[i] < (int)neigh[i].size() && idx[neigh[i][idx[i]]] >= 0) ++idx[i];
    if(idx[i] == (int)neigh[i].size()) {  // 无剩余可访问的子节点
      stk.pop();                          // 回溯
      continue;
    }
    idx[neigh[i][idx[i]]] = 0;   // 表示访问 neigh[i][idx[i]] 之后从下标 0 开始搜索子节点
    stk.push(neigh[i][idx[i]]);  // 当前访问的节点变为 neigh[i][idx[i]]
    // 见 solve()，如果 idx[i] >= parfix[i]，表示 neigh[i][idx[i]] 的父节点并非 i，而是之前已经确定
    if(par[stk.top()] < 0 || idx[i] < parfix[i]) par[stk.top()] = i;
    ++idx[i];  // 更新当前节点父节点的访问进度
    return true;
  }
  return false;
}

// 干预 next() 的执行，贪心拆环，最小化字典序
void solve()
{
  bool loop_broken = false;  // 环只能拆一次
  looped.assign(n, false);
  for(int i = 0; i < (int)loop.size(); ++i) looped[loop[i]] = true;
  idx.assign(n, -1), par.assign(n, -1), parfix.assign(n, n);

  // 遍历从编号最小的节点开始
  int i = 0;
  idx[i] = 0;
  stk.push(i);
  cout << i + 1 << ' ';

  while(next()) {
    int j = stk.top();  // 当前访问的节点编号

    // 拆环算法（干预 next() 原本的深度优先策略）
    if(!loop_broken && looped[par[j]] && looped[j]) {
      stk.pop();     // 尝试跳过 j，实现拆环
      if(!next()) {  // 无后续元素，不可跳过
        stk.push(j);
      } else {
        int k = stk.top();  // 后续元素
        if(j < k) {         // 跳过后字典序增大，撤销跳过
          stk.pop();        // 将 k 出栈并标记为未访问，但保留其祖先 par[k]
          idx[k] = -1;
          stk.push(j);  // 恢复原定当前访问元素 j，并把 k 添加为 j 的子节点，推迟 k 的访问
          // “固定” k 的祖先，避免其意外地成为 j；只有 k 通过其他原有图边被先访问到，k 的祖先才发生改变
          // parfix[j] 后的“子节点”祖先均被“固定”
          parfix[j] = min(parfix[j], (int)neigh[j].size());
          neigh[j].push_back(k);
        } else {                 // 跳过后字典序减小，应当跳过
          loop_broken = true;    // 打拆环标记
          idx[j] = par[j] = -1;  // 撤销对 j 的访问记录
          j = k;                 // 将当前访问的节点改成 k
        }
      }
    }

    cout << j + 1 << ' ';
  }
}

int main()
{
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  neigh.resize(n);
  for(int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v, --u, --v;
    neigh[u].push_back(v);
    neigh[v].push_back(u);
  }
  for(int i = 0; i < n; ++i) sort(neigh[i].begin(), neigh[i].end());
  if(m == n - 1) {
    solve_tree(0), cout << endl;
    return 0;
  }
  dfn.assign(n, -1), low.assign(n, -1);
  for(int i = 0; i < n; ++i) {
    if(dfn[i] >= 0) continue;
    tarjan(i);
    if(!loop.empty()) break;
  }
  solve(), cout << endl;
  return 0;
}

题解：P5049 [NOIP 2018 提高组] 旅行加强版

文章操作

相关推荐

评论

题解：P5049 [NOIP 2018 提高组] 旅行加强版