题解分析

1. 题意理解

你会得到$T$组数据。对于每组数据，会给出$n$个矩形，每个矩形由左上角坐标$(y_1, x_1)$、右下角坐标$(y_2, x_2)$以及期望颜色$c$来描述。染色要遵循规则：只有当一个矩形上方的所有矩形都染完色，这个矩形才能染色，且必须一次性染完整个矩形。目标是找出最少的换色次数来完成所有矩形的染色。

2. 思路分析

• 拓扑排序的依据：一个矩形可以控制它正下方紧挨着的矩形，也就是说，必须先给没有被控制的矩形染色，这符合拓扑排序的思想。拓扑排序能帮助我们确定矩形染色的先后顺序。
• 暴力搜索的原因：数据范围$n < 15$，这个规模比较小。因此可以使用暴力搜索的方法，通过枚举所有可能的染色顺序，来找到最少的换色次数。

3. 具体实现步骤

步骤一：构建图和拓扑排序信息

• 首先要构建矩形之间的依赖关系图，用邻接表来表示。
• 同时统计每个矩形的入度（即有多少个矩形控制它）。

步骤二：拓扑排序

• 把入度为$0$的矩形加入队列。
• 依次从队列中取出矩形，更新与之相邻矩形的入度，若相邻矩形入度变为$0$，则将其加入队列。

步骤三：暴力搜索

• 利用深度优先搜索（$DFS$）来枚举所有可能的染色顺序。
• 在搜索过程中，记录当前的换色次数，并且更新最小换色次数。

4. 复杂度分析

• 时间复杂度：拓扑排序的时间复杂度是$O(n^2)$，而暴力搜索的时间复杂度是$O(n!)$，因为要枚举所有可能的排列。
• 空间复杂度：主要的空间开销在于图的邻接表和递归栈，空间复杂度是$O(n^2)$。

标程

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>

// 不使用 using namespace std; 以避免命名冲突
// 定义矩形结构体
struct node {
    int x1, x2, y1, y2;
    int id, c;
};

// 定义全局变量
struct node ar[21];
std::vector<int> lin[21];
int ans, n, T;
int in[21];
int vis[21];

// 深度优先搜索函数
void dfs(int tot, int step, int nowc) {
    if (step >= ans) {
        return;
    }
    if (tot == n) {
        ans = step;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0 && vis[i] == 0) {
            for (int j = 0; j < lin[i].size(); j++) {
                in[lin[i][j]]--;
            }
            vis[i] = 1;
            if (nowc == ar[i].c) {
                dfs(tot + 1, step, nowc);
            } else {
                dfs(tot + 1, step + 1, ar[i].c);
            }
            vis[i] = 0;
            for (int j = 0; j < lin[i].size(); j++) {
                in[lin[i][j]]++;
            }
        }
    }
}

int main() {
    // 读取测试用例数量
    scanf("%d", &T);
    while (T--) {
        // 读取矩形数量
        scanf("%d", &n);
        ans = 999999;
        for (int i = 1; i <= n; i++) {
            // 读取矩形信息
            scanf("%d %d %d %d %d", &ar[i].y1, &ar[i].x1, &ar[i].y2, &ar[i].x2, &ar[i].c);
            ar[i].id = i;
            // 清空邻接表
            lin[i].clear();
            // 初始化入度和访问标记
            in[i] = 0;
            vis[i] = 0;
        }
        // 建图，即建立控制关系
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (ar[j].x1 < ar[i].x2 && ar[j].x2 > ar[i].x1 && ar[j].y1 == ar[i].y2) {
                    lin[i].push_back(j);
                    in[j]++;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0 && vis[i] == 0) {
                vis[i] = 1;
                for (int j = 0; j < lin[i].size(); j++) {
                    in[lin[i][j]]--;
                }
                dfs(1, 1, ar[i].c);
                vis[i] = 0;
                for (int j = 0; j < lin[i].size(); j++) {
                    in[lin[i][j]]++;
                }
            }
        }
        // 输出结果
        printf("%d\n", ans);
    }
    return 0;
}