Codeforces 1209D Cow and Snacks
2024-10-07 00:25:34
题目大意
有 $n$ 个不同的糖果,从 $1$ 到 $n$ 编号。有 $k$ 个客人。要用糖果招待客人。
对于每个客人,这些糖果中恰有两个是其最爱。第 $i$ 个客人最爱的糖果编号是 $x_i$ 和 $y_i$ 。
将 $k$ 个客人任意排列,他们按顺序去拿自己最爱的糖果。
客人要拿到至少一个最爱的糖果才满意。
求不满意的客人的最小数目。
数据范围
- $2 \le n \le 10^5$
- $1 \le k \le 10^5$
- $1 \le x_i, y_i \le n$, $x_i \ne y_i$
分析
这道题可以用图(graph)来刻画。
将 $n$ 个糖果看成 $n$ 个点。
把第 $i$ 个客人看成连接 $x_i, y_i$ 的无向边。
客人拿糖果可以看成从图中删掉对应的边,并将与这条边关联的端点也取走。
客人被满足等价于删边时至少有一个端点还在。
不难看出,一个连通分量有 $c$ 个点意味着有且最多有 $c - 1$ 个客人能被满足。
设共有 $C$ 个连通分量,则有且至多有 $N - C$ 个客人能被满足。
最新文章
- oracle查看对象信息
- Map工具系列-06-销售营改增历史数据处理工具
- Non Lasting Storage File System、procfs、sysfs
- svn update错误
- 4.20-4.24程序设计基础结束,UID课程
- Prime Path 分类: 搜索 POJ 2015-08-09 16:21 4人阅读 评论(0) 收藏
- OpenJudge计算概论-点和正方形的关系【判断点是否在正方形内部】
- xe5 android sample 中的 SimpleList 是怎样绑定的
- C++将类的构造函数、析构函数声明为private或者protected的用途
- WPF中使用ValueConverter来实现“范围条件触发器”
- JavaSE复习日记 : 抽象类
- Java IO学习笔记(二)缓冲流
- ASP.NET MVC 解决区域和全局控制器同名的问题
- 终结python协程----从yield到actor模型的实现
- PIL库自我学习总结及应用(美白,磨皮,搞笑图片处理)
- jQuery使用(三):DOM操作之val()方法操作表单元素value值
- Vue(九) 自定义指令
- 6-14 Abbott的复仇 uva816
- python 回溯法 子集树模板 系列 —— 10、m着色问题
- ios测试宏指令出错:“Expected identefier”