回归梦想

分类

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

TA的专栏 41篇文章 0人订阅

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共1124篇）

NC106972 Cow Ski Area

NC106972 Cow Ski Area 题目： • N*M的滑雪场，每个点都有他的高度，滑雪的时候只能向四周相邻的不高于当前点的高度的点滑，现在滑雪场准备修建若干个缆车线路，使得奶牛可以从任意一个点运动到滑雪场的每个点，问最少需要建多少条缆车线路。题解：本质还是有向图，通过加边使其强连通• ...

** tarjan 缩点

2021-01-14

0 575

NC51269 Network of Schools

NC51269 Network of Schools 题目：给你一张有向图，问最少要加几条边才能使得图上的点都属于同一个强连通分量题解：加边变成强连通分量缩点之后，入度为0的点和出度为0的点两两连边，多随便一连——答案就是max（入度为0的点数，出度为0的点数）处理后：代码： #inclu...

** tarjan 缩点

2021-01-14

0 640

NC50403 [ZJOI2004]嗅探器

NC50403 嗅探器题目： • 某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快...

*** tarjan 割点

2021-01-14

1 795

NC20603 [ZJOI2007]最大半连通子图

NC20603 [ZJOI2007]最大半连通子图题目： • 一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。• 若G'=(V',E')满足V'∈V，E'是E...

拓扑排序 **** tarjan 缩点

2021-01-14

0 717

第1节连通性强连通、割点和桥（一）

@[toc] 无向图割点、桥、双连通分量 • 给定无向联通图G=（V,E） • 对于一个点x，若从图中删除x及所有与x相连的边，图不再联通，x是G的割点• 对于一条边e，从图中删去e，图不再联通，e的x的割边• 一个图如果不存在割点，则它是一个点双连通图，一个图的极大点双连通子图是他的点双连通分量。...

tarjan 强连通图

2021-01-14

0 613

NC107617 poj3020 Antenna Placement

问题： n * m的矩阵，有一些障碍点，用12的骨牌覆盖所有非障碍点 (12骨牌可重叠，骨牌可越界，骨牌可延伸到障碍点) 问最少需要多少个。题解： • 尽量用一个骨牌覆盖两个格子，覆盖不了了再重叠使用骨牌• 用和上一个题一样的方式求一个最大匹配，那么就有（2 * 最大匹配）个点已经被覆盖了• 剩...

二分图匹配 **

2021-01-14

0 585

NC51272 棋盘覆盖

题目：给出一张n×n(n≤100) 的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。题解：先进行黑白染色，相邻的两个黑白就是一个骨牌，又因为一个格子不能放多个骨牌，所以相当于找每个格子的搭档（搭档即为相邻的点），使得搭档的数量足够多裸的二分图最大匹配代码：

二分图匹配 ***

2021-01-14

0 779

二分图匹配(二)

@[toc] 例题： NC20483 [ZJOI2009]假期的宿舍题目描述：学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直...

二分图匹配题目集h

2021-01-13

0 688

NC107638 poj3041 Asteroids

题目描述：网格图中有若干个陨石，每次发射武器可以打掉某一行或某一列的所有陨石，求打完所有陨石的最少次数题解：首先，贪心的打星球最多的行/列有反例，如： 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 正解：我们把行和列抽象为点，把陨石抽象为边，即当（x,y）有一个陨石的...

二分图匹配匈牙利算法

2020-12-16

0 608

NC51316 Going Home

题目描述： n 个小人回到 n 间房子，要求一对一，告诉每个人的位置和每个房子的位置，问n个人移动的总距离最少是多少题解：最小权值匹配模板我们分别记录人和房，然后人与房连边并记录边权将所有边权值取相反数，然后跑一遍最优权值匹配模板详细看代码，仔细看看怎么构造图代码： #include<i...

二分图匹配最优匹配

2020-12-16

2 545