#3410. 「2020-2021 集训队作业」小 Z 的摸鱼计划

题目描述

小 Z 是一个很菜的 OI 选手，他有一个 $n$ 个点 $m$ 条边的简单连通无向图，点从 $0,\ldots,n-1$ 编号，边从 $0,\ldots,m-1$ 编号，编号为 $i$ 的边连接点 $U_i$ 和 $V_i$。

小 Z 现在不想做题，于是他想了一个摸鱼计划：首先，他用铅笔在纸上写下了一个 $0,\ldots,n-1$ 的排列 $p_0,\ldots,p_{n-1}$。然后，他会多次进行操作：随机选出一条图上的边 $u,v$，交换 $p_u$ 和 $p_v$ 的值。

由于某些原因，如果某个时刻，排列 $p$ 满足对于所有 $0\le i \le n-1$ 都有 $p_i=i$，小 Z 就会突然想起自己有多菜并停止摸鱼。小 Z 不想让这种情况发生，所以，如果你告诉小 Z 一种通过 $k$ 次这样的操作使排列 $p$ 满足 $p_i=i$ 的方案，他就会在至多进行 $k-1$ 次操作之后停止摸鱼，这时我们认为小 Z 在摸鱼上花费的代价为 $k$。特别地，如果小 Z 第一次操作前 $p$ 就满足 $p_i=i$，那么小 Z 在摸鱼上花费的代价为 $0$。

由于你知道小 Z 很菜，而且快要省选了，你想要破坏小 Z 的摸鱼计划。于是你找到了小 Z，一边强行给他讲知识点，一边对他的摸鱼计划进行破坏：你的每次操作可以选出两个整数 $0 \le u,v < n$，然后交换 $p_u$ 和 $p_v$ 的值。$u,v$ 可以相同，这表示你的这步操作不改变排列 $p$。在你的每次操作之后，你可以选择继续操作，或者结束操作并告诉小 Z 一种从此时的排列 $p$ 开始，在小 Z 的 $k$ 次操作后对所有 $i$ 都满足 $p_i=i$ 的方案，使得小 Z 接下来在摸鱼上花费的代价为 $k$。如果你选择继续操作，小 Z 可以先进行一次操作 (他也可以选择跳过)：选出一条边 $u,v$，然后交换 $p_u$ 和 $p_v$ 的值，然后再次由你操作。(小 Z 不能主动让你停止操作)

小 Z 希望，在你结束操作后，接下来花费在摸鱼上花费的代价尽可能大。你希望，在你结束操作之后，小 Z 接下来在摸鱼上花费的代价尽可能小。小 Z 事先请小 U 帮他算出了如果双方都采取最优策略，小 Z 花费在摸鱼上的代价。所以如果你成功地使小 Z 花费在摸鱼上的代价小于等于这个值，小 Z 会深深地感觉到自己和你的水平差距并停止摸鱼，所以你会获得这个测试点 $100\%$ 的分数。如果你仅仅算出了双方都采取最优策略时小 Z 花费在摸鱼上的代价，但是没能给出方案，小 Z 也会感觉到自己和你的水平差距，但是他不会停止摸鱼，所以你会获得这个测试点 $30\%$ 的分数。

如果你的前 $T$ 次操作后没有决定结束，小 Z 会拒绝让你继续操作，这时他会认为你无法给出一个合法方案，在这种情况下你至多能获得这个测试点 $30\%$ 的分数。

题解

问题分析

这是一道交互题，核心是计算图的最大交换距离。给定一个连通图 $G=(V,E)$，定义其交换直径 $D(G)$ 为：

$$D(G) = \max_{\pi \in S_n} \min_{\text{操作序列}} \{\text{通过边交换将排列}\ \pi\ \text{恢复成恒等排列所需步数}\} $$

其中操作只能交换图中边连接的两个顶点的值。

核心思路

1. 问题转化

设图 $G$ 的边集为 $E$。一个排列 $\pi$ 可以通过图中的边交换操作排序，当且仅当 $\pi$ 的所有循环都可以通过图的边进行交换。

对于排列 $\pi$ 的一个循环 $(a_1\ a_2\ \ldots\ a_k)$，要分解这个循环需要至少 $k-1$ 次交换操作。

2. 图的连接性分析

• 树结构：每个连通分量最多只能分解有限类型的循环
• 完全图：任何排列都可以在 $O(n)$ 步内排序
• 一般图：需要分析图的连通性和结构

3. 博弈策略分析

我们是先手，可以通过交换任意位置的 $p$ 值来重新排列。小 Z 是后手，只能通过图中的边交换。我们的目标是最大化小 Z 恢复恒等排列所需的最小步数。

解决方案

1. 理论计算

设图 $G$ 的连通分量为 $G_1, G_2, \ldots, G_c$，大小分别为 $n_1, n_2, \ldots, n_c$。则：

$$D(G) = \sum_{i=1}^c D(G_i)$$

其中 $D(G_i)$ 是连通分量 $G_i$ 的交换直径。

2. 连通分量的交换直径计算

对于一个连通分量 $H$ 有 $k$ 个顶点：

1. 如果 $H$ 是树：

   • $D(H) = k - 1$
   • 证明：可以构造一个大循环 $(0\ 1\ \ldots\ k-1)$，需要 $k-1$ 次边交换才能恢复

2. 如果 $H$ 包含环：

   • 设 $H$ 的最小生成树边数为 $k-1$
   • 额外边数 $e = m_H - (k-1)$，其中 $m_H$ 是 $H$ 的边数
   • $D(H) = k - \min(1, e)$
   • 解释：环的存在可以减少恢复步数

3. 特殊情况：

   • 完全图：$D(H) = k-1$
   • 环图（$k$ 个点的环）：$D(H) = k-1$

3. 算法步骤

1. 找到图的所有连通分量
2. 对每个连通分量 H_i：
   - 计算其大小 k_i
   - 判断是否为树
   - 计算 D(H_i)
3. 总答案 = Σ D(H_i)

具体实现

代码框架

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

vector<int> adj[MAXN];
bool vis[MAXN];

// DFS 寻找连通分量
int dfs(int u, vector<int>& comp) {
    vis[u] = true;
    comp.push_back(u);
    int cnt = 1;
    for (int v : adj[u]) {
        if (!vis[v]) {
            cnt += dfs(v, comp);
        }
    }
    return cnt;
}

// 判断连通分量是否为树
bool is_tree(const vector<int>& comp) {
    unordered_set<int> comp_set(comp.begin(), comp.end());
    int edge_count = 0;
    
    for (int u : comp) {
        for (int v : adj[u]) {
            if (comp_set.count(v)) {
                edge_count++;
            }
        }
    }
    edge_count /= 2; // 每条边被计数两次
    
    return edge_count == comp.size() - 1;
}

// 计算连通分量的交换直径
int compute_diameter(const vector<int>& comp) {
    int k = comp.size();
    
    if (is_tree(comp)) {
        return k - 1;
    }
    
    // 对于有环图
    unordered_set<int> comp_set(comp.begin(), comp.end());
    int edge_count = 0;
    
    for (int u : comp) {
        for (int v : adj[u]) {
            if (comp_set.count(v)) {
                edge_count++;
            }
        }
    }
    edge_count /= 2;
    
    // 额外边数
    int extra_edges = edge_count - (k - 1);
    return k - min(1, extra_edges);
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 读入图
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 找连通分量
    vector<vector<int>> components;
    memset(vis, 0, sizeof(vis));
    
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            vector<int> comp;
            dfs(i, comp);
            components.push_back(comp);
        }
    }
    
    // 计算总交换直径
    int total_diameter = 0;
    for (auto& comp : components) {
        total_diameter += compute_diameter(comp);
    }
    
    cout << total_diameter << endl;
    
    return 0;
}

交互实现

#include "graph.h"
#include <bits/stdc++.h>
using namespace std;

// 全局变量
int n, m, T;
vector<int> U, V, p;
vector<vector<int>> adj;

// 计算答案
int compute_answer() {
    // 1. 建立邻接表
    adj.resize(n);
    for (int i = 0; i < m; i++) {
        int u = U[i], v = V[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 2. 寻找连通分量
    vector<bool> visited(n, false);
    int total = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            vector<int> comp;
            queue<int> q;
            q.push(i);
            visited[i] = true;
            
            int edges_in_comp = 0;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                comp.push_back(u);
                
                for (int v : adj[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.push(v);
                    }
                    // 统计边数（会被重复统计）
                    edges_in_comp++;
                }
            }
            
            edges_in_comp /= 2; // 修正边数
            int k = comp.size();
            
            // 3. 计算该分量的交换直径
            if (edges_in_comp == k - 1) {
                // 树
                total += k - 1;
            } else {
                // 有环图
                total += k - 1; // 简化处理，实际需要更精确
            }
        }
    }
    
    return total;
}

// 构造最坏排列
vector<int> construct_worst_permutation() {
    vector<int> worst_p(n);
    // 简单构造：反序排列
    for (int i = 0; i < n; i++) {
        worst_p[i] = n - 1 - i;
    }
    return worst_p;
}

// 主函数
pair<pair<int, int>, vector<int>> Solve(int _n, int _m, int _T, 
                                       vector<int> _U, vector<int> _V, 
                                       vector<int> _p, int subtask) {
    n = _n; m = _m; T = _T;
    U = _U; V = _V; p = _p;
    
    // 1. 计算理论最优值
    int optimal_cost = compute_answer();
    Answer(optimal_cost);
    
    // 2. 构造最坏排列（通过交换操作）
    vector<int> target_perm = construct_worst_permutation();
    
    // 3. 找到从当前排列到目标排列的交换序列
    vector<pair<int, int>> my_swaps;
    
    // 简单策略：逐个将元素放到正确位置
    vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        pos[p[i]] = i;
    }
    
    for (int i = 0; i < n; i++) {
        if (p[i] != target_perm[i]) {
            int j = pos[target_perm[i]];
            // 交换 p[i] 和 p[j]
            my_swaps.push_back({i, j});
            swap(p[i], p[j]);
            swap(pos[p[i]], pos[p[j]]);
        }
    }
    
    // 4. 执行交换操作
    pair<int, int> last_swap = {0, 0};
    if (!my_swaps.empty()) {
        // 执行前 T-1 次交换
        for (int i = 0; i < min((int)my_swaps.size(), T - 1); i++) {
            auto [u, v] = my_swaps[i];
            Swap(u, v);
        }
        
        // 最后一次交换作为返回值
        if (!my_swaps.empty() && my_swaps.size() <= T) {
            last_swap = my_swaps.back();
        }
    }
    
    // 5. 构造小 Z 的恢复方案（简化版本）
    vector<int> recovery_plan;
    // 这里需要根据具体图结构构造恢复方案
    // 简化：使用任意可行的边交换序列
    
    return {last_swap, recovery_plan};
}

特殊情况处理

1. 链（子任务2-4）

当图是一条链 $(0-1-2-\cdots-n-1)$ 时：

• $D(G) = n-1$
• 最坏排列：反序排列 $(n-1, n-2, \ldots, 0)$
• 恢复方案：依次交换边 $(0,1), (1,2), \ldots, (n-2, n-1)$

2. 树（子任务5）

对于任意树：

• $D(G) = n-1$
• 证明：构造一个大循环排列 $(0\ 1\ \ldots\ n-1)$，需要沿着树路径依次交换

3. 完全图

• $D(G) = n-1$
• 任何排列最多需要 $n-1$ 次交换

复杂度分析

• 时间复杂度：$O(n + m)$
• 空间复杂度：$O(n + m)$

注意事项

1. 交互规则：

   • 必须在 Solve 开始时调用 Answer(x)
   • Swap 调用必须在 Answer 之后
   • 最多调用 $T$ 次 Swap

2. 数值范围：

   • $n, m \le 10^5$
   • 代价不超过 $10^7$

3. 图的性质：

   • 图保证连通
   • 排列 $p$ 是合法的排列

总结

本题的核心是计算图的最大交换距离。通过分析图的连通分量结构，可以计算出理论最优值。交互部分需要正确实现 Answer 调用和操作序列返回。实际实现时需要考虑如何构造最坏排列和相应的恢复方案。

关键点：

1. 理解交换直径的概念
2. 分析图的结构对交换能力的影响
3. 正确实现交互协议
4. 构造可行的操作序列

对于不同子任务，可以针对图的结构（链、树、一般图）进行优化实现，以获得更好的性能。