Posts tagged with Graph


emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易想到是最小割了,但是没想到具体的建图方法。 题意: 有n个点,m条边,要你分成两个集合,使得两个集合的导出子图各自权值和的和最大。 两个导出子图中,可选择其中一个,若导出子图中存在有两个点 (i,j) 相连,则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反,只有存在两个点没有边相连,才会增加权值。 思路: 题目的主要目的就是将点集分成两部分,这很容易想到二分图染色,但这是不现实的,因为这是一个最值问题,不存在必然关系。…

对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。 题意: 给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。 思路: 首先询问很多,有$4\times10^5$个询问,直接一个一个找肯定是不行的。 但是值得注意的是,…

网络流建图神题!!! 同时也是2015年北京现场赛的金牌题,虽然我不可能去挑战金牌,但是也只有做这种神题,尽管不是自己想得,但A了之后仍然充满了满足。 题意: 给你一个DAG,表示一个游戏的技能树,也就是说某一些技能存在前置技能,但实际上这是为氪金大佬准备的游戏,有钱是真的可以为所欲为的,大佬们可以选择花钱直接无视所有前置技能直接习得某一个技能,也可以消除掉两个技能之间的依赖关系。 现在某个节俭的大佬想要学某一个技能,问最小花费。 思路: 说实话这道题一眼真的很容易想到图上DP,但是存在可以消除一个依赖的权利,使得DP存在后效性。 正解是最小割建模,这个最小割建模真的是非常巧妙: 拆点建图,u -&…

一眼以为是状压DP…… 但是仔细读题的话,会有一个致命条件是状压无法解决的。 偷看了一下薛昊的博客,回去路上还跟我说二分图不可能建出来,结果到头来却用HK写这题。 题意: 给你一张图,是矩阵的形式,在满足条件的情况下你要选择尽可能多的格子。 其条件如下 如果选中一个格子,这个格子是数字,则相同数字的格子立刻被选中。 每个被选中的格子不允许其四个相邻的格子中 存在被选中且与其不同的格子 思路: 实际上这道题的确很想状压,如果把题目中的第一个条件改成,与其选中格子联通且数字相同的格子立马被选中的话,状压可解。但事实并非如此。 其实可以把所有是数字且相同的格子作为一个点,每个 . 也作为一个点,…

一个三元环计数问题…… 当然是转化出来的…… 一开始没想到去计数三元环的思路,而是直接搜…… 然后发现题目理解错了…… 又发现这特么不就跟三元环数量有关么?? 巧的是薛昊之前问过我三元环计数,我还特意去看了几眼。不然真的可能卡不出来。 题意: 给你一张无向图,让你计数这样的子图。 V=(A,B,C,D) , E=(AB,BC,CD,DA,AC) 思路: 一开始我以为必须是矩形,…