分类 - 图论

? 解题记录 ? ? 网络流 ? ? 最大流 ?    2021-01-27 11:14:26    1547    0    0
链接标题 复习最小路径覆盖 最小路径覆盖是指对于给定的DAG,用最少的路径将其所有点覆盖,路径不相交。最小路径覆盖建图如下: 变式1:最小链覆盖 用最少的路径将其所有点覆盖,路径可以相交 做法:使用floyd传递闭包重连边,然后进行最小路径覆盖 变式2:最长反链 指选择最多的点,使得两两之间不能互相到达 做法:对偶问题:最长反链等于最小链覆盖 本题中发现球是依次加入的,如果有两个球和为完全平方数那么小的向大的连接单向边,一个柱子就相当于一条路径。那么可以知道K" role="presentation" style="position: relative;"&
2020-09-14 13:41:50    893    0    0
以前一直以为自己写的点分治找对了重心。结果前几天自己写代码的时候,发现重心父亲一端子树的重心有问题。因为代码里传的子树大小是错误的,传的是当前根下父亲的子树大小而不是真正的大小。 当时感性想了一下发现卡不掉,最多也就是常数差别。今天发现原来这个问题已经有严格证明,所以可以放心这么“错误”地写点分啦~ >证明点我<
? 解题记录 ? ? FFT|NTT ? ? 树链剖分 ? ? 虚树 ? ? 组合数 ?    2019-03-18 12:09:49    1156    0    3
题目描述 给你一棵n个点的树,每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是:把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来,求:有多少种方案可以使每种颜色交集产生的树非空。对k&#x2208;[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k
? 解题记录 ? ? LOJ ? ? 字典树 ?    2019-03-14 15:26:58    558    0    0
题目链接 题解:发现只需要分两段维护就可以了。 上一次排过序的前缀部分用字典树维护,并且对每一位记录nowxor" role="presentation">nowxornowxornow_xor表示按照当前的顺序,第i" role="presentation">iii位是否被翻转。后面的部分用一个前缀和维护。 这样的话,异或的时候维护偏移值,每一次排序我们就把后面的部分全部插入字典树,并且更新now&#x005F;xor" role="presentation">now_xornow_xornow\_xor。 #include<cstdio&g
? 解题记录 ? ? LOJ ? ? 树链剖分 ? ? FFT|NTT ? ? 动态规划 ?    2019-03-14 11:31:06    738    0    0
题目链接:传送门 题解:不难发现,我们有一个优秀的N2N^2的dpdp做法,记录f(i,j,0/1)f(i,j,0/1)表示ii子树内选jj个,当前根选没选。 我们要知道分治NTTNTT的复杂度:对于kk个总度数∑deg=k\sum deg=k的多项式来说,计算它们乘积的复杂度可以做到:O((∑deg)log(∑deg)logk)O((\sum deg)log(\sum deg)logk)。 因此,我们采用重链剖分,先转移所有轻链。 不难发现, g(u,0)=∏v∈son(g(v,0)+g(v,1))g(u,0)=\prod_{v\in son} (g(v,0)+g(v,1))
? 解题记录 ? ? LOJ ? ? 带权二分 ? ? 动态规划 ?    2018-12-10 09:18:19    335    0    0
题目描述 小 L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做 “LCT” 的挑战,它的规则是这样子的:现在有一个 NN 个点的树(Tree),每条边有一个整数边权 vi" role="presentation">viviv_i,若 vi&#x2265;0" role="presentation">vi≥0vi≥0v_i \ge 0,表示走这条边会获得 vi" role="presentation">viviv_i的收益;若 vi&
? 解题记录 ? ? 洛谷 ? ? 网络流 ? ? 上下界网络流 ?    2018-12-05 23:08:48    339    0    0
题目描述滑雪场坐落在FJ省西北部的若干座山上。 从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。 你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。 由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。 输入输出格式输入格式:   输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。 接下来的n行,描述1
? 解题记录 ? ? 强连通分量 ? ? 洛谷 ?    2018-11-13 10:01:47    472    0    0
题目描述在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙,而又非常聪明,他费尽心机谋划了这次盗窃行动,破解重重机关后来到这座地下宫殿前。 整座宫殿呈矩阵状,由R×C间矩形宫室组成,其中有N间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室
? 解题记录 ? ? 洛谷 ? ? 最短路 ?    2018-11-13 09:12:52    409    0    0
题目描述小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面, 华容道是否根本就无法完成,如果能完成, 最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的: 在一个 n×m 棋盘上有n×m个格子,其中有且只有一个格子是空白的,其余n×m−1个格子上每个格子上有一个棋子,每个棋子的大小都是 1×1 的; 有些棋子是固定的,有些棋子则是可以移动的; 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以
? 解题记录 ? ? 洛谷 ? ? Floyd ?    2018-10-21 15:29:58    616    0    0
题目描述参加jsoi冬令营的同学最近发现,由于南航校内修路截断了原来通向计算中心的路,导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路,却没有使路程增加,因为可以找到同样长度的路作替代。其实,问题的关键在于,路截断的地方是交通要点。 同样的情况也出现在城市间的交通中。某些城市如果出了问题,可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题,于是决定研究这个问题。 他们认为这样的城市是重要的:如果一个城市c被破坏后,存在两个不同的城市a和b(a, b均不等于c),a到b的最短距离增长了(或不通),则城市