Posts tagged with Graph


首先说一下这道题的思路真的是非常巧妙。 但是,出题人脑子进shi了么,难道一定要写法和你一样才能过???? 反正卡的特别紧,我到最后还有一个测试点一直超时。 时间限制是 1200s ,明显就是故意的。这种故意卡常在51Nod里巨特么多。搞不懂他们在想什么。 不觉得会在以后碰到类似的题目会故意卡我,因为很多人都是 1000 ~ 1200 的时间卡过的。 题意: 给你一个有向图,让你任意改动边的方向,使得出入度相同的点数最多。 并输出方案。 思路: 一眼看成上下界网络流。实际上这道题就是用上下界网络流改出来的,但就别想了,…

Havel定理判定简单图 被上下界网络流烦傻了,暂时不想写代码太长的题。 虽然是一道水题,但也是建立在一定理论基础上的。 再科普一下简单图,没有重边没有自环的图就是简单图。区别有向图和无向图,也就是说,有向图的反向边不算重边。 给定一个非负整数序列{dn},若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。进一步,若图为简单图,则称此序列可简单图化 可图化的判定: ( \sum_{i=1}^{n}d_{i} mod…

别多说了,神题。 写不来,看得是大佬的题解 很妙,没想到用二分图染色,但是二分图染色的模型的确很适合这个题目。 不过关键还是那个判定定理。 题意: 给你一个序列,要你用两个栈给它排序,问你这个序列是否能排序成功。 思路: 上面的链接很详细,我这里简单说一蛤。 首先必须注意到判定两个数必须在两个不同的栈的充要条件。 S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i&…

无汇源上下界可行流的模板题。 说是模板题,其实想让它除了二分以外加点变化也是有点困难的。 关于上下界网络流的问题,以前偷懒没学,本来打算这几天补上,加上今天薛昊这个催化剂又来问我,于是就今天开始补了。 在这里我非常非常非常非常非常推荐这篇博文 总结的非常详细,写的有十分通俗易懂,全文十分连贯,评论也有人说看完给人一种荡气回肠的感觉。 当我看完无汇源上下界可行流的时候,我马上敲了一蛤这道题,就一 A 了。妙啊! 下面简单说一下无汇源上下界可行流的解法,不详细说明,具体请看上面的链接。 无汇源上下界可行流可用建图+最大流解决,建图方式如下:…

LCA 好题! 这道题我暂时只知道用Tarjan的解法。 Tarjan解法完美地运用了Tarjan的核心原理与性质: 深度优先搜索时的向下局部性。自己乱取得,蛤蛤蛤 题意: 给你一棵树,每个节点有一个权值。给你很多个询问,每个询问两个点。要你在给定点的树链上找到有序的最大差值。 思路: 首先考虑分治。设树链 u -> lca -> v 答案无非只有三种情况: u…