emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易想到是最小割了，但是没想到具体的建图方法。 题意： 有n个点，m条边，要你分成两个集合，使得两个集合的导出子图各自权值和的和最大。 两个导出子图中，可选择其中一个，若导出子图中存在有两个点 (i,j) 相连，则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反，只有存在两个点没有边相连，才会增加权值。 思路： 题目的主要目的就是将点集分成两部分，这很容易想到二分图染色，但这是不现实的，因为这是一个最值问题，不存在必然关系。 而跟二分图相关的只有网络流了，将图分为两半是割的概念，当然只存在最小割，正面去想的话，就是总权值和-最小割。 然后……思路就断了，找不到有效的建图方法。 可以先这么想，我们假定与源点相连的点集为相连增加权值的集合，并称之为，与汇点相连的点集则相反，称之为汇点集。 那么我们先将每个点都与源点相连，其容量为将该点加入源点集所能增加的权值。 再将这个点与汇点相连，其容量为将该点加入汇点集所能增加的权值。 此时直接跑最小割是不对的，因为这些点并不是独立的。…
对Tarjan的算法理解有点要求的题，之前看了一下思路，敲了一下结果没过，照着博客改动了一下但并没有搞懂，今天补上。 题意： 给你一个有向图，若干询问，询问为从 s 到 t 的最小字典序路径中，第 k 个点是哪个点。 思路： 首先询问很多，有$4\times10^5$个询问，直接一个一个找肯定是不行的。 但是值得注意的是，点数比较少，只有$3000$个，假如我们固定起点，遍历全图来获得路径，在遍历的同时，对每一个点来记录答案。理想复杂度为$O(N^2)$，时间上满足条件。 一个问题是如何保证字典序最小，emmmm 用vector记录整张图，对于每个点的边进行排序，因为每个点访问一次，解决之。 这题还有一个合理的大坑，如果在遍历的时候，在之前已经出现了一个环，那么之后的所有点就都不会被访问。 当然你不能在找到一个环后，后面的点就不再遍历，…
网络流建图神题！！！ 同时也是2015年北京现场赛的金牌题，虽然我不可能去挑战金牌，但是也只有做这种神题，尽管不是自己想得，但A了之后仍然充满了满足。 题意： 给你一个DAG，表示一个游戏的技能树，也就是说某一些技能存在前置技能，但实际上这是为氪金大佬准备的游戏，有钱是真的可以为所欲为的，大佬们可以选择花钱直接无视所有前置技能直接习得某一个技能，也可以消除掉两个技能之间的依赖关系。 现在某个节俭的大佬想要学某一个技能，问最小花费。 思路： 说实话这道题一眼真的很容易想到图上DP，但是存在可以消除一个依赖的权利，使得DP存在后效性。 正解是最小割建模，这个最小割建模真的是非常巧妙： 1. 拆点建图，u -> u’ 的容量是直接氪金习得这一技能的花费 2. 如果u,v存在依赖关系 u -> v ，建边 u’ -> v ，容量为消除这个依赖的费用 3. 将源点与每一个技能连边，容量为按技能树学习的费用。 4. 将所要求的技能与汇点相连，容量为 inf 最后跑一遍最大流就是答案。 网上很多题解到这里就没了，也没有一个像样点的解释。 对于学习技能来说，…
一眼以为是状压DP……
但是仔细读题的话，会有一个致命条件是状压无法解决的。
偷看了一下薛昊的博客，回去路上还跟我说二分图不可能建出来，结果到头来却用HK写这题。
题意：
给你一张图，是矩阵的形式，在满足条件的情况下你要选择尽可能多的格子。
其条件如下
* 如果选中一个格子，这个格子是数字，则相同数字的格子立刻被选中。
* 每个被选中的格子不允许其四个相邻的格子中 存在被选中且与其不同的格子
思路：
实际上这道题的确很想状压，如果把题目中的第一个条件改成，与其选中格子联通且数字相同的格子立马被选中的话，状压可解。但事实并非如此。
其实可以把所有是数字且相同的格子作为一个点，每个 . 也作为一个点，再将其与四周连边，按题意来的话，略加思考，其实就是个最大独立集的裸题。
但是关键还是需要转化出来啊……
坑点，答案最小为 1 。
AC Code
#include
一个三元环计数问题……
当然是转化出来的……
一开始没想到去计数三元环的思路，而是直接搜……
然后发现题目理解错了……
又发现这特么不就跟三元环数量有关么？？
巧的是薛昊之前问过我三元环计数，我还特意去看了几眼。不然真的可能卡不出来。
题意：
给你一张无向图，让你计数这样的子图。
V=(A,B,C,D) ， E=(AB,BC,CD,DA,AC)
思路：
一开始我以为必须是矩形，然后发现同一点的不同三元环都满足条件。
所以我只要找到这个点的所有三元环数量，任意挑出两个即可。记得去重
个人三元环计数方法如下：
首先枚举每一条遍，再判断两个端点，确定度数较少的点，从这个点进行扩展一条边，再判断这条遍的另一端是否有边与第一条边的另一端点相连。
其中有很多细节值得优化，比如说对于( sqrt(m) )为分界进行不同的判定。
AC Code
#include
首先说一下这道题的思路真的是非常巧妙。 但是，出题人脑子进shi了么，难道一定要写法和你一样才能过？？？？ 反正卡的特别紧，我到最后还有一个测试点一直超时。 时间限制是 1200s ，明显就是故意的。这种故意卡常在51Nod里巨特么多。搞不懂他们在想什么。 不觉得会在以后碰到类似的题目会故意卡我，因为很多人都是 1000 ～ 1200 的时间卡过的。 题意： 给你一个有向图，让你任意改动边的方向，使得出入度相同的点数最多。 并输出方案。 思路： 一眼看成上下界网络流。实际上这道题就是用上下界网络流改出来的，但就别想了，正解都卡着过，网络流能过？ 建图方式和无汇源上下界可行流一致，跑一遍最大流即可。 下面是另一种思路。 有入度相同的特征的图还有一种，就是欧拉图，对于度数为奇数的点(以下简称奇点，反之偶点），必然不可能存在一个方案使得其出入点相同。这是必然的，那么反过来对于偶点，如果欧拉路径存在也就必然存在一个方案使得其出入度相同。 直接将所有奇点，顺序两两相连，跑一遍欧拉路径即可。 这里补充两点 1. 奇点数量必然为偶数。因为每一条遍贡献的…
Havel定理判定简单图 被上下界网络流烦傻了，暂时不想写代码太长的题。 虽然是一道水题，但也是建立在一定理论基础上的。 再科普一下简单图，没有重边没有自环的图就是简单图。区别有向图和无向图，也就是说，有向图的反向边不算重边。 给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化 可图化的判定： ( \sum_{i=1}^{n}d_{i} mod 2 == 0 ) 。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。 可简单图化的判定（Havel定理）： 把序列排成不增序，即 ( d_1 \geq d_2 \geq \ldots \geq d_n )，则d可简单图化当且仅当 ( d’ = \left{ d_2-1 , d_…
别多说了，神题。
写不来，看得是大佬的题解
很妙，没想到用二分图染色，但是二分图染色的模型的确很适合这个题目。
不过关键还是那个判定定理。
题意：
给你一个序列，要你用两个栈给它排序，问你这个序列是否能排序成功。
思路：
上面的链接很详细，我这里简单说一蛤。
首先必须注意到判定两个数必须在两个不同的栈的充要条件。
S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i