回归梦想

分类

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人学习

全部文章（共29篇）

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包题目：给定一些点，问围住所有点所用的围栏的长度题解：凸包模板题凸包详细代码： #include<iostream> #include<algorithm> #include&l...

** 凸包计算几何

2021-01-23

0 863

[USACO09FEB]Revamping Trails G

题意：约翰一共有 N 个牧场.由 MM 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 1 出发到牧场 N 去给奶牛检查身体。通过每条小径都需要消耗一定的时间。约翰打算升级其中 K 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 0。请帮助约...

** 分层图

2021-01-18

0 767

NC51307 Redundant Paths

NC51307 Redundant Paths 题目： • 给定无向连通图，求至少需要添加几条边使它变成一个边双连通图。（添多少边可以消灭所有的桥）题解：先用边双连通缩点• 缩点之后是一棵树• 无根树的叶子（度数为1的点）都需要再添一条边，叶子节点两两连接• 答案是是（叶子数+1）/2 代码：...

** tarjan 缩点

2021-01-14

0 527

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

NC107617 poj3020 Antenna Placement

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

二分图匹配 **

2021-01-14

0 584

NC20483 [ZJOI2009]假期的宿舍

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

二分图匹配匈牙利算法 **

2020-12-15

2 602

CF741C Arpa’s overnight party and Mehrdad’s si

题目描述：有n对情侣（2n个人）围成一圈坐在桌子边上，每个人占据一个位子，要求情侣不能吃同一种食物，并且桌子上相邻的三个人的食物必须有两个人是不同的，只有两种食物（1或者是2），问一种可行分配方式。题解：如果我们能把不能吃同一种食物的人连边，问题就变成二分图黑白染***r>• 所以情侣关...

** 01染色二分图

2020-12-15

0 670

H - Fight Against Monsters

题意： n个怪兽，各自的攻击力atk和生命值hp给出，让英雄去杀死所有的怪物规则：英雄对于一个怪物，伤害等于攻击次数，英雄在攻击怪物前先受到怪物攻击，伤害为所有怪物的攻击力，回合制进行，问英雄杀死所有怪物最少受到多少伤害？题解：其实很简单，我们只需要按照性价比排序，将攻击强命脆的怪物先攻击即可但...

** ing 贪心

2020-11-26

1 607