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.

算法分析

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

代码

#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);
++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;
}

418 I'm a teapot