回归梦想

题解

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)

/ 注册

全部文章 / 题解（共270篇）

NC107617 poj3020 Antenna Placement

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

二分图匹配 **

2021-01-14

0 584

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

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

P3806 【模板】点分治1

模板题 P3806 【模板】点分治1 题目描述给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。详讲关于点分治具体内容可以看这个这里主要是详细讲讲代码： getrt是用来求重心，我们利用树型dp的思维来做，即找到该节点所有的子树，找到最大的哪一颗即可 void getr...

2020-12-02

0 417

POJ2155 - Matrix（二维树状数组）

POJ2155 - Matrix 文章目录题目题解：代码题目给你一个二维矩阵，初始化为0，然后可以进行两次操作： C:x,y,x1,y2 对该小矩阵内的数进行取反 Q:查询某个点是0还是1 题解： C是区间...

2020-12-02

0 496

Matrix Subtraction（小米icpc邀请赛第一场）

Matrix Subtraction 题意：一个给定的矩阵，然后给定一个子矩阵的大小，子矩阵可以将覆盖矩阵的区域的值减1，问能否将矩阵全部减为0 题解：思路和下面这个链接讲的题十分相似传送本质就是二维树状数组差分求解用mp数组来存矩阵，然后对空白的data数组进行构造，构造完对m...

2020-12-02

0 694