题解 | #和谐并处的车#

题目链接

和谐并处的车

题目描述

在一个 $N \times N$ 的棋盘上，有 $M$ 个“车”，初始时它们两两不互相攻击（即任意两个车都不同行也不同列）。

一个“车”可以沿其所在的行或列移动任意格。移动的目标是，在移动后，它仍然不能被任何其他的车攻击。

你需要计算出最少的移动步数，使得所有 $M$ 个车都位于棋盘的主对角线上（即形如 $(i, i)$ 的格子）。

解题思路

这是一个经典的图论建模问题。问题的核心是识别出“车”的位置关系所形成的结构，并计算移动它们以解除依赖所需的最小代价。

1. 建模为有向图

我们可以将棋盘的行和列编号 ( $1, \dots, N$ ) 视作图的顶点。每个“车”的位置 $(r, c)$ 可以被看作是一条从顶点 $r$ 指向顶点 $c$ 的有向边 $r \to c$ 。

由于初始时所有车都不同行也不同列，这意味着：

每个顶点最多只有一条出边。
每个顶点最多只有一条入边。

满足这种性质的图，其结构必然是由若干个不相交的路径和环组成。

2. 分析目标和移动

目标：将所有车移动到主对角线。一个位于 $(r, c)$ 的车，最终需要移动到某个 $(d, d)$ 的位置。最理想的情况是移动到 $(r, r)$ 或 $(c, c)$ 。
已在对角线的车：如果一个车的位置是 $(i, i)$ ，它已经满足了要求，不需要移动。在我们的图模型中，这对应一个自环 $i \to i$ 。
不在对角线的车：一个位于 $(r, c)$ （其中 $r \neq c$ ）的车，需要移动。这至少需要 1 步。

3. 路径与环的移动策略

路径 (Path)：考虑一条由车构成的路径，例如 $p_1 \to p_2 \to p_3$ 。这对应于两个车，分别在 $(p_1, p_2)$ 和 $(p_2, p_3)$ 。
- 车 $(p_2, p_3)$ 想移动到 $(p_2, p_2)$ ，但它的目标列 $p_2$ 被车 $(p_1, p_2)$ 占据。
- 车 $(p_1, p_2)$ 想移动到 $(p_1, p_1)$ ，它的目标列 $p_1$ 是空的（因为 $p_1$ 是路径起点，没有入边）。
我们可以从路径的终点开始，逐个将车移动到对角线位置。
1. 移动车 $(p_1, p_2) \to (p_1, p_1)$ 。这需要 1 步。
2. 现在列 $p_2$ 空出来了，可以移动车 $(p_2, p_3) \to (p_2, p_2)$ 。这需要 1 步。
对于一条由 $k$ 个车（即 $k$ 条边）构成的路径，我们总共需要 $k$ 步移动。
环 (Cycle)：考虑一个由 $k$ 个车构成的环，例如 $p_1 \to p_2 \to \dots \to p_k \to p_1$ 。
- 车 $(p_1, p_2)$ 无法移动到 $(p_1, p_1)$ ，因为列 $p_1$ 被车 $(p_k, p_1)$ 占据。
- 同理，环上的每一个车的目标位置都被环上的另一个车所占据，形成了一个“死锁”。
要打破这个死锁，我们需要一个额外的步骤：
1. 将环上任意一个车，比如 $(p_1, p_2)$ ，移动到一个临时的、安全的空行/空列。这需要 1 步。
2. 现在列 $p_2$ 空出来了，车 $(p_2, p_3)$ 可以移动到 $(p_2, p_2)$ 。
3. ...依次移动，直到车 $(p_k, p_1)$ 移动到 $(p_k, p_k)$ 。这需要 $k-1$ 步。
4. 最后，将临时的车从它的临时位置移动到最终位置 $(p_1, p_1)$ 。这需要 1 步。
对于一个由 $k$ 个车构成的环，我们总共需要 $k+1$ 步移动。

4. 最终公式

综合以上分析，总的最小移动步数为： 总步数 = (所有需要移动的车 C 的数量) + (C 构成的图中环的数量)

5. 算法实现：使用并查集

我们可以使用并查集 (DSU) 来高效地找出这些路径和环的结构。

初始化并查集，每个顶点 $1, \dots, N$ 都是一个独立的集合。
为每个集合（用其根节点表示）维护一个标志位 is_cycle，初始为 false。
遍历所有不在对角线上的车 $(r, c)$ :
- 首先，总步数加 1，因为这个车至少要移动一次。
- 查找 $r$ 和 $c$ 的根节点 root_r 和 root_c。
- 如果 root_r == root_c：这说明加入 $r \to c$ 这条边，使得 root_r 所在的连通分量形成了一个环。如果这个分量之前不是环（!is_cycle[root_r]），我们就将它标记为环，并且总步数额外加 1。
- 如果 root_r != root_c：我们将这两个集合合并。合并后的新集合的 is_cycle 状态是两个旧集合状态的“或”运算。

最终得到的总步数即为答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

vector<int> parent;

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        parent[b] = a;
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    parent.assign(n + 1, 0);
    iota(parent.begin(), parent.end(), 0);
    
    int moves = 0;
    for (int i = 0; i < m; ++i) {
        int r, c;
        cin >> r >> c;
        if (r == c) {
            continue;
        }

        moves++;
        int root_r = find_set(r);
        int root_c = find_set(c);

        if (root_r == root_c) {
            moves++;
        } else {
            unite_sets(r, c);
        }
    }
    cout << moves << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static int[] parent;

    private static int findSet(int v) {
        if (v == parent[v]) {
            return v;
        }
        return parent[v] = findSet(parent[v]);
    }

    private static void uniteSets(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();

            parent = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }

            int moves = 0;
            for (int i = 0; i < m; i++) {
                int r = sc.nextInt();
                int c = sc.nextInt();

                if (r == c) {
                    continue;
                }

                moves++;
                int rootR = findSet(r);
                int rootC = findSet(c);

                if (rootR == rootC) {
                    moves++;
                } else {
                    uniteSets(r, c);
                }
            }
            System.out.println(moves);
        }
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(200005)

parent = []

def find_set(v):
    if v == parent[v]:
        return v
    parent[v] = find_set(parent[v])
    return parent[v]

def unite_sets(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        parent[b] = a

def main():
    global parent
    
    tokens = sys.stdin.read().split()
    if not tokens:
        return
        
    t = int(tokens[0])
    token_idx = 1

    for _ in range(t):
        n = int(tokens[token_idx])
        m = int(tokens[token_idx + 1])
        token_idx += 2
        
        parent = list(range(n + 1))
    
        moves = 0
        for _ in range(m):
            r = int(tokens[token_idx])
            c = int(tokens[token_idx + 1])
            token_idx += 2
            
            if r == c:
                continue
            
            moves += 1
            root_r = find_set(r)
            root_c = find_set(c)

            if root_r == root_c:
                moves += 1
            else:
                unite_sets(r, c)
                
        print(moves)

if __name__ == "__main__":
    main()

算法及复杂度

算法：并查集 (DSU)
时间复杂度： $\mathcal{O}(M \cdot \alpha(N))$ 。对于 $M$ 个车，我们执行 $M$ 次并查集操作。每次操作的均摊时间复杂度为 $\alpha(N)$ （反阿克曼函数），在实践中可视为常数。
空间复杂度： $\mathcal{O}(N)$ ，用于存储并查集的 parent 数组。