有一个包含 $\displaystyle n$个顶点和 $\displaystyle n-1$ 条边的无向图,已知顶点 $\displaystyle i$ 和 $\displaystyle i+1$ 之间有一条边相连 $(1 \leq i \leq n-1 )$。 现在需要断开 $\displaystyle m$ 对顶点之间的连接,每对顶点用 $( a{j},b{j} )$ 表示 $(1 \leq j \leq m )$。 问:最少需要断开多少条边,才能满足题目要求。

举个例子:比如 $\displaystyle n=5$,有 $\displaystyle 2$ 对顶点需要断开,分别为 $(1,3)$ 和 $(2,4)$,那么只需要断开 $\displaystyle 2-3$ 的边即可满足要求,答案等于 $\displaystyle 1$。如下图所示:

输入格式 第 $\displaystyle 1$ 行输入两个正整数 $\displaystyle n$ 和 $\displaystyle m \ (2 \leq n \leq 10^{5}, 1 \leq m \leq 10^{5})$ 。 第 $2 - m+1$ 行每行输入一个点对 $a{i}$ 和 $b{i} \ (1 \leq a{i} ,b{i} \leq n, a{i} \neq b{i} , 1 \leq i \leq m)$。

输出格式 输出答案。

数据范围 $2 \leq n \leq 10^{5}, 1 \leq m \leq 10^{5}$ $1 \leq a{i} ,b{i} \leq n, a{i} \neq b{i} , 1 \leq i \leq m$

输入样例:

5 2
1 3
2 4

输出样例:

1

题目分析

注意题目条件 已知顶点 i 和 i+1 之间有一条边相连,所以此题与 并没有什么关系,可以想象成一条线段,需要断开的是一些区间。而我们的目标就是用尽量少的断点来切断所有的区间。

那么什么样的断点方法最优呢?

我们可以先简单考虑下面两种断点方案:

  • 两个区间没有交叉。这个时候,我们无论怎么断,需要的断点数都是两个,没有差别。

  • 两个区间有交叉。这个时候,我们只需要在两个区间的交叉部分断开一个点,就可以将两个区间都隔断。所以尽管区间有交叉,我们的断点数也是一个。

相较于简单地对每一个区间切一个断点,第二种情况明显优化了断点的数量。所以这里就显现出来我们的贪心思想——当多个区间有交叉时,找到共同交叉的地方断开,能够保证使用较少的断点。

按照这个思想,我们在代码中需要按照顶点对的右端点排序,然后从有最小右端点的开始,逐一判断是否需要切断。这样做是因为最小右端点的区间有最大可能与后面的区间发生交错,所以我们按照这一策略就可以切断尽可能多的区间。

要证明这种贪心算法确实得到了全局最优解。我们可以设任意一个最优解至少有一条边 e,这条边不在贪心策略选择的边集合中。我们可以在这个最优解的基础上,用贪心策略选择的边替换掉边 e,因为贪心策略选择的边都是符合所有约束条件且右端点最小的,所以替换之后不会增加所需断开的边的数量,还可能减少。因此,基于贪心策略的解就是一个最优解,所以我们的贪心策略是正确的。

代码实现

#include <iostream>
#include <algorithm>
#define x first 
#define y second
using namespace std;
using PII = pair <int, int>;
const int N = 1e5 + 10;
using namespace std;

PII p[N];
int n, m, a, b;
int main() {
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        cin >> p[i].x >> p[i].y;
        if(p[i].x > p[i].y) swap(p[i].x, p[i].y);
    }
    sort(p, p + m, [](const PII& a, const PII& b) {
        return a.y < b.y;
    });
    int cnt = 0;
    int edge = -0x7ffffff;
    for(int i = 0; i < m; ++i) {
        if(p[i].x >= edge) {
            edge = p[i].y;
            ++cnt;
        }
    }
    cout << cnt;
    return 0;
}
分类: SortThought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status