[BZOJ 4238] 电压

题目大意

给定一个 nn 个节点,mm 条边的无向图(可能有重边,可能不连通),求有多少条边满足:边的两个节点同色,对剩下的图可以黑白着色。

2n10,0002 \leqslant n \leqslant 10,000

1m20,0001 \leqslant m \leqslant 20,000

题目链接

BZOJ 4238

题解

所求的边一定在所有的奇环上,同时不在任何一个偶环上。

对图进行 dfs,当遇到环时,通过节点深度差判断环的奇偶(差是奇数时是偶环。。。)。具体实现时,为深度大的点的权值 +1+ 1,为小的 1- 1,子节点 dfs 后用子节点的权值更新父节点。

(我好菜啊,Po 姐的题解我没有看懂。。。T_T)

使用静态分配内存加速

当你很喜欢用 new 却有担心动态分配内存会超时时,可以使用静态分配内存。

大概就像这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <new>

struct Edge {
Node *u, *v;
Edge *next;
Edge() {}
Edge(Node *u, Node *v) :u(u), v(v), next(u->e) {}
} _pool[MAXM << 1], *_cur = _pool;

void addEdge(int u, int v) {
N[u].e = new (_cur++) Edge(&N[u], &N[v]);
N[v].e = new (_cur++) Edge(&N[v], &N[u]);
}

对于这道题,在 BZOJ 上,动态分配内存运行了 4872s,静态分配内存运行了 4044s。(好吧,好像加速得不是太多。。。)

另外,以这种方式创建的对象,**一定不能用 delete **。

代码

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
#include <cstdio>
#include <new>
const int MAXN = 100005;
const int MAXM = 200005;
struct Edge;
struct Node {
Edge *e;
Node *fa;
int circleCnt[2], deep;
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next, *rev;
bool vis;
Edge() {}
Edge(Node *u, Node *v) : u(u), v(v), vis(false), next(u->e) {}
} _pool[MAXM << 1], *_cur = _pool;
void addEdge(int u, int v) {
N[u].e = new (_cur++) Edge(&N[u], &N[v]);
N[v].e = new (_cur++) Edge(&N[v], &N[u]);
N[u].e->rev = N[v].e;
N[v].e->rev = N[u].e;
}
int n, m;
int circleCnt[2];
void dfs(Node *u) {
for (Edge *e = u->e; e; e = e->next) {
if (e->vis) continue;
if (e->v->deep == 0) {
e->v->deep = u->deep + 1;
e->vis = e->rev->vis = true;
e->v->fa = u;
dfs(e->v);
u->circleCnt[0] += e->v->circleCnt[0];
u->circleCnt[1] += e->v->circleCnt[1];
} else {
if (e->v->deep <= u->deep) {
int x = ((u->deep - e->v->deep) & 1) ^ 1;
u->circleCnt[x]++;
e->v->circleCnt[x]--;
circleCnt[x]++;
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
}
for (int i = 1; i <= n; i++) {
if (N[i].deep == 0) {
N[i].deep = 1;
dfs(&N[i]);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (N[i].fa && N[i].circleCnt[0] == 0
&& N[i].circleCnt[1] == circleCnt[1]) ans++;
}
if (circleCnt[1] == 1) ans++;
printf("%d\n", ans);
return 0;
}