[BZOJ 1064][NOI 2008] 假面舞会

题目大意

对一个有向图进行染色,要求同一个节点的所有的子节点必须同色,同一个节点的所有父节点必须同色,相连的两个节点不许同色。求最大。

\(1\leqslant n \leqslant 100,000\)

\(1 \leqslant m \leqslant 1,000,000\)

\(k \geqslant 3\) (颜色数)

题目链接

BZOJ 1064

CodeVS 1800

题解

感觉这是道神题吧(我好菜啊)。。。

首先,有两种情况:环和树。对于一个单向环,答案为其长度的约数(多个环就是公约数);对于单向树,答案为任意大于等于 \(3\) 的数,最大为树上最长链长。对于不是单向的结构,我们发现,形如 A->B<-C->D 的结构可以由 A->B 替换(显然有 A 与 C 同色,B 与 D 同色),这样,我们可以把所有的结构转化为单向结构。为了方便进行上述操作,我们对于每一条有向边赋权值 \(1\),同时添加一条反向边,权值为 \(-1\),这样按一个方向绕一圈回来(可由 dfs 实现)的权值和的绝对值就是环对应单向环的长度。

具体实现:进行 dfs 为节点编号,编号为上一个节点的编号 + 边权,当下一个点的编号已确定时,表明找到了一个环,新编号与旧编号的差的绝对值为环对应单向环的长度;对于树,进行 dfs 编号,最大最小编号差 \(+1\) 即为最长单向链长。

代码

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
#include <cstdio>
#include <climits>
#include <algorithm>
// #define DBG
const int MAXN = 100005;
struct Edge;
struct Node {
Edge *firstEdge;
int no, wcc;
#ifdef DBG
int id;
#endif
bool vis;
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next, *rev;
int w;
bool vis;
Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->firstEdge) {}
};
void addEdge(int u, int v, int w = 1) {
#ifdef DBG
printf("edge: %d --> %d\n", u, v);
#endif
N[u].firstEdge = new Edge(&N[u], &N[v], w);
N[v].firstEdge = new Edge(&N[v], &N[u], -w);
N[u].firstEdge->rev = N[v].firstEdge;
N[v].firstEdge->rev = N[u].firstEdge;
}
int C[MAXN], circleCnt;
struct WCC {
int min, max;
} wcc[MAXN];
int wccCnt;
int n, m;
void findCircle(Node *u, int no = 1) {
#ifdef DBG
printf("findCircle: node-%d, no-%d\n", u->id, no);
#endif
u->no = no;
u->vis = true;
for (Edge *e = u->firstEdge; e; e = e->next) {
if (e->vis) continue;
#ifdef DBG
printf("..egde: %d --> %d, w = %d, to->vis = %d\n", u->id, e->v->id, e->w, e->v->vis ? 1 : 0);
#endif
e->vis = e->rev->vis = true;
if (!e->v->vis) findCircle(e->v, no + e->w);
else {
#ifdef DBG
printf("..node: %d\n", u->id);
#endif
if (no + e->w - e->v->no != 0) C[++circleCnt] = abs(no + e->w - e->v->no);
}
}
}
void clear() {
for (int i = 1; i <= n; i++) {
N[i].vis = false;
for (Edge *e = N[i].firstEdge; e; e = e->next) e->vis = false;
}
}
void findWCC(Node *u) {
#ifdef DBG
printf("findWCC : node-%d\n", u->id);
#endif
u->wcc = wccCnt;
for (Edge *e = u->firstEdge; e; e = e->next) if (!e->v->wcc) findWCC(e->v);
}
void dfs(Node *u, int no = 1) {
u->no = no;
u->vis = true;
for (Edge *e = u->firstEdge; e; e = e->next) {
if (!e->v->vis) dfs(e->v, no + e->w);
}
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
scanf("%d %d", &n, &m);
#ifdef DBG
for (int i = 1; i <= n; i++) N[i].id = i;
#endif
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
}
for (int i = 1; i <= n; i++) {
if (!N[i].vis) findCircle(&N[i]);
}
#ifdef DBG
printf("circleCnt = %d\n", circleCnt);
#endif
if (circleCnt == 0) {
for (int i = 1; i <= n; i++) {
if (!N[i].wcc) {
wccCnt++;
wcc[wccCnt].min = INT_MAX;
wcc[wccCnt].max = INT_MIN;
findWCC(&N[i]);
}
}
clear();
for (int i = 1; i <= n; i++) {
if (!N[i].vis) dfs(&N[i]);
wcc[N[i].wcc].min = std::min(wcc[N[i].wcc].min, N[i].no);
wcc[N[i].wcc].max = std::max(wcc[N[i].wcc].max, N[i].no);
}
int ansMax = 0;
for (int i = 1; i <= wccCnt; i++) ansMax += wcc[i].max - wcc[i].min + 1;
if (ansMax >= 3) printf("%d 3\n", ansMax);
else puts("-1 -1");
return 0;
}
int gcdC = C[1];
for (int i = 2; i <= circleCnt; i++) gcdC = gcd(gcdC, C[i]);
int lcdC;
for (lcdC = 3; lcdC <= gcdC; lcdC++) if (gcdC % lcdC == 0) break;
if (gcdC >= 3) {
printf("%d %d\n", gcdC, lcdC);
return 0;
}
puts("-1 -1");
return 0;
}