彩色路径

GitHub跳转原题关系图 Canvas 关系图返回列表

按最多 4 条边分成前后两段做彩色路径 DP，再用位集查询颜色不冲突的最佳后半段。

OJ: shumeng

题目 ID: CSP202312E

难度:提高+/省选-

标签:图论状压 DP折半搜索位运算

日期: 2026-07-31 16:21

形式化题目

给定一个带正边权有向图，节点有颜色。求从 0 到 $n-1$ 的最长路径，要求路径上节点颜色互不相同，且节点数不超过 $l$ 。其中 $l\le 9$ ，颜色数 $k\le 30$ 。

思路

先看小数据 DFS 枚举所有路径的程序，它直接按颜色互异剪枝：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
// brute.cpp：小数据暴力解，DFS 枚举所有长度不超过 l 的彩色路径。
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to, weight;
};

int n, m, limit, color_count;
vector<int> color;
vector<vector<Edge> > graph;
long long answer;

void dfs(int node, int depth, int mask, long long length) {
    if (node == n - 1) answer = max(answer, length);
    if (depth == limit) return;
    for (int i = 0; i < (int)graph[node].size(); i++) {
        Edge edge = graph[node][i];
        int bit = 1 << color[edge.to];
        if (mask & bit) continue;
        dfs(edge.to, depth + 1, mask | bit, length + edge.weight);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> limit >> color_count;
    color.resize(n);
    for (int i = 0; i < n; i++) cin >> color[i];
    graph.resize(n);
    vector<int> from(m), to(m), length(m);
    for (int i = 0; i < m; i++) cin >> from[i];
    for (int i = 0; i < m; i++) cin >> to[i];
    for (int i = 0; i < m; i++) cin >> length[i];
    for (int i = 0; i < m; i++) graph[from[i]].push_back({to[i], length[i]});

    answer = 0;
    dfs(0, 1, 1 << color[0], 0);
    cout << answer << '\n';

    return 0;
}

在中间节点折半

路径最多有 $l-1\le 8$ 条边。枚举路径中的中间节点 $v$ ，把路径拆成两段：

从 0 到 $v$ 的前半段，最多 4 条边；
从 $v$ 到 $n-1$ 的后半段，最多 4 条边。

两段都包含 $v$ 。若去掉两段各自的中间颜色，那么剩余颜色集合必须不相交；合并后的节点数为“左边边数 + 右边边数 + 1”，不超过 $l$ 即可。因为颜色不同会自动保证不会重复经过同一个节点，所以不必担心节点重复。

两侧状压 DP

forward[d][v][mask] 表示从 0 出发走 $d$ 条边到达 $v$ 、颜色集合为 mask 时的最大长度；backward[d][v][mask] 对应从 $v$ 出发走 $d$ 条边到达终点。只保留 $d\le 4$ 的状态，每次沿边转移并拒绝已经出现过的颜色。

用位集合并最优后半段

对于固定中间节点和一个前半段颜色集合，需要在后半段状态中找到颜色集合不相交且长度最大的状态。

把后半段状态按长度限制分别按权值降序排列；对每个颜色维护一个候选下标位集。查询时，把前半段包含颜色对应的位集取并集，剩余的最低位就是第一个不被占用的候选，也就是长度最大的可行后半段。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

const long long NEGATIVE = -(1LL << 60); // 表示不可达的极小值

struct Edge {
    int to;     // 边的终点
    int weight; // 边的长度
};

// 后半段候选状态的索引：按权值降序排列，并用位集记录每个颜色出现在哪些候选里
struct CandidateIndex {
    vector<long long> value;                    // 候选按权值降序排列的长度
    vector<vector<unsigned long long> > conflict; // conflict[c][w] 表示颜色 c 在候选区间 w 内占用了哪些位
};

int n, m, limit, color_count;
vector<int> color;                        // 每个节点的颜色标签
vector<vector<Edge> > graph, reverse_graph; // 原图与反向图

// 候选状态按长度降序排序
bool compare_candidate(const pair<int, long long> &left,
        const pair<int, long long> &right) {
    return left.second > right.second;
}

// 对某个中间节点 node 建立后半段候选索引。
// states 是某方向的状态表，middle_color 是要去掉的中间节点颜色（两段都包含它）。
CandidateIndex build_index(const vector<vector<unordered_map<int, long long> > > &states,
        int node, int middle_color, int maximum_depth) {
    vector<pair<int, long long> > candidate;
    for (int depth = 0; depth <= maximum_depth; depth++) {
        for (unordered_map<int, long long>::const_iterator it = states[depth][node].begin();
                it != states[depth][node].end(); ++it) {
            // 去掉中间节点的颜色位，避免前后两段重复计算
            candidate.push_back({it->first ^ (1 << middle_color), it->second});
        }
    }
    sort(candidate.begin(), candidate.end(), compare_candidate);

    CandidateIndex result;
    int word_count = ((int)candidate.size() + 63) / 64;
    result.value.resize(candidate.size());
    result.conflict.assign(color_count, vector<unsigned long long>(word_count, 0));
    for (int i = 0; i < (int)candidate.size(); i++) {
        result.value[i] = candidate[i].second;
        // 候选 i 含有的每个颜色，都在对应位集里标记这一位
        for (int bit = 0; bit < color_count; bit++) {
            if (candidate[i].first & (1 << bit)) {
                result.conflict[bit][i >> 6] |= 1ULL << (i & 63);
            }
        }
    }
    return result;
}

// 在候选索引中找与 forbidden 颜色集合不相交的、长度最大的候选。
// 利用位集把 forbidden 包含的颜色对应的位取并集，剩余未占用的最低位即最优候选。
long long find_best(const CandidateIndex &index, int forbidden) {
    int word_count = (index.value.size() + 63) / 64;
    for (int word = 0; word < word_count; word++) {
        unsigned long long unavailable = 0;
        for (int bit = 0; bit < color_count; bit++) {
            if (forbidden & (1 << bit)) unavailable |= index.conflict[bit][word];
        }
        unsigned long long available = ~unavailable;
        if (word == word_count - 1 && index.value.size() % 64 != 0) {
            available &= (1ULL << (index.value.size() % 64)) - 1; // 去掉最后一组多余位
        }
        if (available != 0) {
            int position = word * 64 + __builtin_ctzll(available);
            return index.value[position];
        }
    }
    return NEGATIVE;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> limit >> color_count;
    color.resize(n);
    for (int i = 0; i < n; i++) cin >> color[i];
    graph.resize(n);
    reverse_graph.resize(n);
    vector<int> from(m), to(m), length(m);
    for (int i = 0; i < m; i++) cin >> from[i];
    for (int i = 0; i < m; i++) cin >> to[i];
    for (int i = 0; i < m; i++) cin >> length[i];
    for (int i = 0; i < m; i++) {
        graph[from[i]].push_back({to[i], length[i]});
        reverse_graph[to[i]].push_back({from[i], length[i]});
    }

    // 路径最多 limit-1 条边，折半后每段最多 4 条边
    int depth_limit = min(4, limit - 1);
    // forward[d][v][mask]：从 0 出发走 d 条边到 v，颜色集合为 mask 的最大长度
    // backward[d][v][mask]：从 v 出发走 d 条边到 n-1，颜色集合为 mask 的最大长度
    vector<vector<unordered_map<int, long long> > > forward(
        depth_limit + 1, vector<unordered_map<int, long long> >(n));
    vector<vector<unordered_map<int, long long> > > backward(
        depth_limit + 1, vector<unordered_map<int, long long> >(n));
    forward[0][0][1 << color[0]] = 0;
    backward[0][n - 1][1 << color[n - 1]] = 0;

    // 向两边同时做状压 DP：每次沿一条边转移，拒绝已出现的颜色
    for (int depth = 0; depth < depth_limit; depth++) {
        for (int node = 0; node < n; node++) {
            for (unordered_map<int, long long>::const_iterator it = forward[depth][node].begin();
                    it != forward[depth][node].end(); ++it) {
                for (int i = 0; i < (int)graph[node].size(); i++) {
                    Edge edge = graph[node][i];
                    int bit = 1 << color[edge.to];
                    if (it->first & bit) continue; // 目标颜色已出现过
                    int mask = it->first | bit;
                    long long value = it->second + edge.weight;
                    long long &best = forward[depth + 1][edge.to][mask];
                    if (best < value) best = value;
                }
            }
            for (unordered_map<int, long long>::const_iterator it = backward[depth][node].begin();
                    it != backward[depth][node].end(); ++it) {
                for (int i = 0; i < (int)reverse_graph[node].size(); i++) {
                    Edge edge = reverse_graph[node][i];
                    int bit = 1 << color[edge.to];
                    if (it->first & bit) continue;
                    int mask = it->first | bit;
                    long long value = it->second + edge.weight;
                    long long &best = backward[depth + 1][edge.to][mask];
                    if (best < value) best = value;
                }
            }
        }
    }

    // 枚举中间节点，合并前后两段：两段颜色集合必须不相交
    long long answer = 0;
    for (int node = 0; node < n; node++) {
        int middle_bit = 1 << color[node];
        vector<CandidateIndex> index(depth_limit + 1);
        for (int depth = 0; depth <= depth_limit; depth++) {
            index[depth] = build_index(backward, node, color[node], depth);
        }
        for (int left_depth = 0; left_depth <= depth_limit; left_depth++) {
            for (unordered_map<int, long long>::const_iterator it = forward[left_depth][node].begin();
                    it != forward[left_depth][node].end(); ++it) {
                int right_limit = min(depth_limit, limit - 1 - left_depth);
                if (right_limit < 0) continue;
                // 后半段颜色不能包含前半段已用的颜色（去掉中间的公共颜色）
                int forbidden = it->first ^ middle_bit;
                long long right_value = find_best(index[right_limit], forbidden);
                if (right_value != NEGATIVE) answer = max(answer, it->second + right_value);
            }
        }
    }
    cout << answer << '\n';

    return 0;
}

复杂度

每侧状态数最多为 $O(n\sum_{i=0}^{4}\binom{k-1}{i})$ ，转移复杂度为状态数乘平均出度。合并时每个状态只需扫描 $O(k/64)$ 个机器字，整体在 $n\le 100,\ m\le 5000,\ k\le 30$ 的范围内可行；空间复杂度为状态和位集大小的总和。

总结

路径长度上限很小，适合把路径从中间拆开；颜色互异性可以用最多 30 位的整数掩码表示。折半后再用位集做“不相交集合的最优值”查询，避免枚举前后路径状态的笛卡尔积。

题目来自第 32 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

西西艾弗岛的路线图可以看作是一个具有 $n$ 个节点和 $m$ 条有向边的图。第 $i$ 个节点（ $0 \leq i < n$ ）有一个颜色标签 $c_i \in \{0, 1, \cdots, k-1\}$ ，第 $j$ 条边（ $0 \leq j < m$ ）从节点 $u_j$ 指向节点 $v_j$ ，长度为 $d_j$ 。

对于游客顿顿来说，理想的观光路线应满足以下条件：

是一条从节点 $0$ 到节点 $n-1$ 的简单路径；
是一条彩色路径，即路径上每个节点的颜色标签均不相同；
并且包含的节点数小于或等于 $l$ 。

具体而言，理想的观光路线是一个节点序列，例如 $(t_0, t_1, \cdots, t_{q-1})$ ，满足以下所有要求：

对于每个 $i$ （ $0 \leq i < q-1$ ），存在一条从节点 $t_i$ 到节点 $t_{i+1}$ 的有向边。
$t_0 = 0$ 且 $t_{q-1} = n-1$
对于每对 $i, j$ （ $0 \leq i < j < q$ ），都有 $c_{t_i} \neq c_{t_j}$ 。
$q \leq l$

一条路径的长度定义为边的总长度。你的任务是找到满足游客顿顿所有要求的最长观光路线。

输入格式

从标准输入读入数据。

输入共五行。

输入的第一行包含四个正整数 $n, m, l, k$ ，分别表示图的节点数、边数、理想观光路线的节点数上限和颜色标签范围。

输入的第二行包含 $n$ 个整数 $c_0, c_1, \cdots, c_{n-1}$ ，表示图中每个节点的颜色标签。

接下来输入边的信息。

输入的第三行包含 $m$ 个整数 $u_0,u_1, \cdots, u_{m-1}$ ，表示每条有向边的起点；

输入的第四行包含 $m$ 个整数 $v_0, v_1, \cdots, v_{m-1}$ ，表示每条有向边的终点；

输入的第五行包含 $m$ 个整数 $d_0, d_1, \cdots, d_{m-1}$ ，表示每条有向边的长度。

输入数据保证不存在起点终点相同的边，如 $(u, u)$ ；每条有向边 $(u, v)$ 仅会出现一次，但不排除 $(u, v)$ 和 $(v, u)$ 可能同时存在。

输出格式

输出到标准输出。

输出一个数，表示理想观光路线的最大长度。

input1

1
2
3
4
56 9 4 10
0 2 2 3 3 9
0 0 0 1 1 1 2 3 4
1 2 4 3 4 5 4 5 5
1 2 4 3 2 8 5 3 1

output1

样例解释

以下是示例图，其中黑色和红色数字分别表示节点编号和边的长度。

如下表所示，在不超过四个节点的限制下，共有五条从节点 $0$ 到节点 $5$ 的彩色路径。其中最长的一条是 $(0, 1, 5)$ ，长度为 $9$ 。

彩色路径	节点数	长度
$(0,1,3,5)$	$4$	$7$
$(0,1,4,5)$	$4$	$4$
$(0,2,4,5)$	$4$	$8$
$(0,1,5)$	$3$	$9$
$(0,4,5)$	$3$	$5$

子任务

全部的测试数据满足：

$2\le n\le 100$
$1\le m\le 5000$
$2\le l\le 9\le k\le 30$
$c_0=0,c_{n-1} = k-1$
$\forall\ i\ (1\le i\le n - 2),\ 1 \leq c_i \leq k-2$
$\forall\ j\ (0\le j<m),\ 0\le u_j,v_j<n,\ c_{u_j}\ne c_{v_j},\ 1\le d_j\le 10^6$
至少存在一条从节点 $0$ 到节点 $n-1$ 的彩色路径，节点数不超过 $l$ 。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	特殊性质
1	20	$\forall\ i\ (0\le i<n-1),\ c_i\le c_{i+1}\\ \forall j\ (0\le j<m),\ u_j<v_j$
2	30	$k\le 15$
3	50	无

彩色路径

目录

形式化题目

思路

在中间节点折半

两侧状压 DP

用位集合并最优后半段

代码

复杂度

总结