P3290-[HNOI2010]平面图判断题解

发表于 分类于 ， 阅读次数：

\(\mathcal{Link}\)

平面图定理

如果一个图 \(G(V,E)\) 是简单平面图，则 \(|E| \le 3|V|-6\)。

为啥捏？假设每一条边都与两个面相邻，则这个平面图可以转化成一个简单多面体。根据欧拉公式： \(|V|-|E|+|M|=2\)（\(|M|\) 表示面）。

考虑面的度数和（就是对偶图上点的度数和）：在对偶图上，度数和正好是 \(2|E|\)；又因为是简单平面图，所以每个面至少有三个度，所以 \(2|E| \ge 3|M|\)。

将 \(|M|\) 代入，则 \(|E| \le 3|V| - 6\)。

思路分析

知道了上面那个定理就很简单了。\(m\) 变成了 \(\mathcal{O}(n)\) 级别，就可以暴力枚举边对。

一条边相对于哈密顿回路的相对位置只有两种：内部或者外部。如果两条边覆盖的哈密顿回路范围有交叉，则这两条边肯定分居内外两侧。则枚举边对，如果覆盖范围有交（不是覆盖），则说明这两段不能在同侧。考虑种类冰茶姬，用 \(i\) 表示边 \(i\) 在内侧，\(i+m\) 表示 \(i\) 在外侧。则将 \(i\) 与 \(j+m\)，\(j\) 与 \(i+m\) 相连，表示如果 \(i\) 在内侧 \(j\) 就必须在外侧。矛盾条件是 \(i\) 与 \(i+m\) 相连。

这里有一个小坑：不要一次性连接 \((i,j+m)\) 与 \((j, i+m)\)，连一条判一条，避免连出环导致递归爆栈。

AC 代码

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
#include <bits/stdc++.h>
using namespace std;

template <class T> 
void read(T &r) {
    r = 0; int ch = getchar(), f = 0;
    while (!isdigit(ch)) { if (ch == 45) f ^= 1; ch = getchar(); }
    while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxm = 1e4 + 5, maxn = 2e2 + 5;
int t, n, m;
int u[maxm], v[maxm], h[maxn], ih[maxn];
int f[maxm << 1];

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

int main() {
    read(t);
    while (t--) {
        read(n); read(m);
        for (int i = 1; i <= m * 2; i++) f[i] = i;
        for (int i = 1; i <= m; i++) {
            read(u[i]); read(v[i]);
        }
        for (int i = 1; i <= n; i++) {
            read(h[i]);
            ih[h[i]] = i;
        }
        if (m > 3 * n - 6) {
            printf("NO\n");
            continue;
        }
        for (int i = 1; i <= m; i++) {
            u[i] = ih[u[i]], v[i] = ih[v[i]];
            if (u[i] > v[i]) swap(u[i], v[i]);
        }
        for (int i = 1; i <= m; i++) {
            for (int j = i + 1; j <= m; j++) {
                if ((u[j] < u[i] && u[i] < v[j] && v[j] < v[i])
                 || (u[i] < u[j] && u[j] < v[i] && v[i] < v[j])) {
                    int i1 = find(i), j2 = find(j + m);
                    if (j2 != i1) f[j2] = i1;
                    int j1 = find(j), i2 = find(i + m);
                    if (j1 != i2) f[j1] = i2;
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            if (find(i) == find(i + m)) {
                printf("NO\n");
                break;
            }
            if (i == m) printf("YES\n");
        }
    }
    return 0;
}