Sarff

图论

ACM个人赛题解(2) CF(1) dp(2) 数论(1) 笔记(5) 题解(29)

/ 注册

全部文章 / 图论（共12篇）

嗅探器

嗅探器题目描述：红蓝军队打演习，蓝军有两个信息中心，红军计划在某个中间服务器上安装一个嗅探器，来获得蓝军情报，而蓝军网络相当庞大，数据包从一个信息中心传到另一个信息中心不止一条路，你需要将嗅探器安装到哪个中间服务器才能保证所有数据包都能被捕获思路：转换一下其实是找割点，但不仅仅是割点，...

链式前向星 tarjan 缩点 dfs

2021-08-14

1 532

Cow Ski Area

Cow Ski Area 题目描述：滑冰，给你一个地图，值代表高度，你只能从高到低滑，相同高度的点可以随便滑，除了根据势能来滑动，你还可以建造传送门，可以无视传送机起点到终点的高度随便走，即双向的，众所周知，传送门很贵，你现在想知道最少造几个传送门使得任意一个点都可以滑到全图所有点思路： ...

链式前向星缩点 tarjan dfs 拓扑排序

2021-08-13

1 367

[ZJOI2007]最大半连通子图

[ZJOI2007]最大半连通子图题目描述：给你一个图G，让你求最大半连通子图拥有的节点数K，以及不同的最大半联通子图的数量C，C要对X取模思路：这是一个比较复杂的题？主要思路是：tarjan缩点+拓扑排序+dp 首先使用tarjan缩点，得到一个有向无环图，缩点的时候需要记录每个点...

链式前向星缩点 tarjan 拓扑排序 dp

2021-08-13

1 421

[HAOI2006]受欢迎的牛

[HAOI2006]受欢迎的牛题目描述：众所周知，喜欢是可以传递的（bushi，给你N头牛，给你M对喜欢关系，如果A喜欢B，B喜欢C，则我们认为A也喜欢C，现在需要求有多少头牛被所有牛喜欢思路：还是先进行tarjan缩点，当且仅当存在一个出度为0的点集，则输出该点集的数量，否则输出0 ...

链式前向星缩点 tarjan 拓扑排序

2021-08-13

1 340

可达性

可达性题目描述：给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。 u1s1，这个题目描述讲的很难懂，你说是阅读理解都不为过，特别是最后一句，什么叫...

tarjan 缩点链式前向星拓扑排序

2021-08-13

0 599

Antenna Placement

Antenna Placement 题目描述： N * M的棋盘中，'o'代表障碍物，'*'代表空位，你可以使用1 * 2的多米诺骨牌放进空格，米牌可以重叠，也可以放在障碍物上，问最少使用多少牌使得放满所有空位思路：和上次那个棋盘问题很相似了，不过这次可以重叠了，那我们只需要计算出最大匹配...

匈牙利算法二分图最大匹配二分图二分图匹配

2021-08-09

1 365

题解 | #棋盘覆盖#

棋盘覆盖题目描述： N * N的棋盘，已知某些位置不能放东西，求最多能往棋盘上放多少块1 * 2的多米诺骨牌，可以横着放，也可以竖着放，且任意两张多米诺骨牌都不重叠思路：都不重叠，就有点像二分图左右两集合内没有边相连的那意思了有点绕其实，因为多米诺骨牌是1 * 2的，我们就将其看成一个...

匈牙利算法二分图最大匹配二分图二分图匹配

2021-08-07

0 505

题解 | #[ZJOI2007]矩阵游戏#

[ZJOI2007]矩阵游戏题目描述：给你一个N*N的矩阵，0代表白色，1代表黑色，你可以任意交换矩阵的两行或两列，问交换若干次能否使得方针的主对角线的颜色均为黑色思路：首先思考一下交换行和交换列的目的交换行，假设该行最终交换到了第 i 行，也就是代表该行的第 i 个元素必须是黑色，...

二分图最大匹配匈牙利算法二分图二分图匹配

2021-08-07

1 489

题解 | #Asteroids#

Asteroids 题目描述：给你一个n*n的地图，地图上有些点有外星生物，你有太空武器，一次可以杀死一行或一列的外星生物，问你最少需要几次攻击能杀死全部的外星生物？思路：感觉这个题见了很多次，但好像又没有写过？贪心是肯定不行的，举个例子：如果挑最多的一行或一列去贪心的选的话就会...

二分图最大匹配匈牙利算法二分图

2021-08-07

0 334

题解 | #Going Home#

Going Home 题目描述：给你一张n * m的地图，里面有若干个小人，用'm'表示，同样的，有相同数量的房子，用'H'表示，每个人可以进入任意一个房子，不过每个房子只能住一个人，现在你需要计算所有人住满房子最少需要走多少步思路：因为房子数量=人的数量，所以是在二分图的完美匹配的基础...

二分图匹配 KM算法二分图完美匹配

2021-08-07

1 403