给定一个 $n$ 个点的竞赛图，给该图的每条边染色，颜色数量不能超过 $m$ 个，一个染色合法当且仅当不存在长度为 $2$ 的路径，即对有向图中任意路径 $i \rightarrow j \rightarrow k$ 均有边 $i \rightarrow j$ 和边 $j \rightarrow k$ 颜色不同

$2 \le n \le 3000, ~ 2 \le m \le 26$

设该竞赛图点集 $V$

考虑染每一种颜色意味着什么，相当于选择一个点集 $S \subseteq V$，将所有边 $(u, v)$ 满足 $u \in S \cap v \in \complement_VS$ 染上该颜色，也就是说我们要找到至多 $m$ 个这样的集合来覆盖所有的边

这样可以给出一个 $m = 2\log n$ 的染色方案，对所有点分治，每次一分为二，给 $S, \complement_V S$ 之间的边按两种方向染上不同的颜色，这样总共需要颜色是 $2\log n$ 的

但实际上可以用二进制来表示这种是否在每个 $S$ 中的关系，对每个 $S_i$，若当前点 $u$ 得到的二进制位为 $1$，则代表 $u \in S_i$，否则 $u \in \complement_VS_i$，即代表 $i$ 不存在颜色为 $i$ 的外向边，那么点 $i$ 的选择方案可以看作 $\{1, 2, …, m\}$ 的一个子集，设为 $A_i$，我们则要选出 $n$ 个集合满足 $\forall i, j$，有 $\exists x, y, ~ x \in A_i, y \in A_j$ 满足 $x \notin A_j, y \notin A_i$

那么一个比较好的构造方法就是取所有大小恰为 $\lfloor\frac{m}2\rfloor$ 的集合，又 $\dbinom{14}{7} = 3432 \ge 3000$，故实际上 $m \le 14$

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>

using namespace std;

const int MAXN = 3432 + 10;

int N, M;
char in[MAXN];

int sve[MAXN]= {0}, m = 0;
void work () {
	int lim = (1 << M) - 1;
	for (int state = 0; state <= lim; state ++) {
		int cnt = __builtin_popcount (state);
		if (cnt == (M >> 1)) sve[++ m] = state;
	}
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), M = getnum ();
	if (M > 14) M = 14;
	work ();
	for (int i = 2; i <= N; i ++) {
		scanf ("%s", in + 1);
		for (int j = 1; j < i; j ++) {
			for (int k = 0; k < M; k ++) {
				if (in[j] == '1' && ((sve[i] >> k) & 1) == 1 && ((sve[j] >> k) & 1) == 0) {
					putchar (k + 'a');
					break;
				}
				if (in[j] == '0' && ((sve[i] >> k) & 1) == 0 && ((sve[j] >> k) & 1) == 1) {
					putchar (k + 'a');
					break;
				}
			}
		}
		puts ("");
	}

	return 0;
}