Conquer the Polygon

题目描述

You have a convex polygon. The vertices of the polygon are successively numbered from $1$ to $n$. You also have a triangulation of this polygon, given as a list of $n-3$ diagonals.

There will be $2n-3$ undirected edges in the graph: $n-3$ edges in the triangulation and $n$ edges on the side of the polygon.

You can choose to conquer some vertices, and if you choose to conquer a vertex, you will conquer all the edges linked to this vertex.

Write a program to determine the minimum number of vertices you need to choose such that you can conquer all the edges. Note that you are not required to conquer all the vertices.

题意概述

给定一个$n$边形的三角剖分，求它的最小点覆盖。

数据范围：$4 \le n \le 10^5$。

算法分析

考虑一个度数为$2$的点：

• 如果这个点已被选择，那么与它相邻的两条边都已被覆盖；
• 否则，为了覆盖与它相邻的边，最优方案是选择与它相邻的两个点。

于是可以将这个点和与它相邻的边删去，又会得到新的度数为$2$的点。可以用类似拓扑排序的方法来维护。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 100005;
int nume, h[N], in[N], used[N], que[N];
struct Edge {
    int v, nxt;
} e[N << 2];

void add_edge(int u, int v) {
    e[++nume] = (Edge) {v, h[u]};
    h[u] = nume;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= 2 * n - 3; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
        ++in[u];
        ++in[v];
    }
    int qb = 0, qe = 0;
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 2) {
            que[qe++] = i;
        }
    }
    for (; qb < qe;) {
        int cur = que[qb++];
        if (!used[cur]) {
            for (int i = h[cur]; i; i = e[i].nxt) {
                if (in[e[i].v] > 2) {
                    used[e[i].v] = 1;
                }
            }
        }
        for (int i = h[cur]; i; i = e[i].nxt) {
            --in[cur];
            --in[e[i].v];
            if (in[e[i].v] == 2) {
                que[qe++] = e[i].v;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += used[i];
    }
    printf("%d\n", ans);
    return 0;
}