tarjan文章列表
[BZOJ1589] [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果（tarjan缩点 + 记忆化搜索）
传送门 先用tarjan缩点，再记忆话搜索一下 #include stack#include cstdio#include cstring#include iostream#define N 1000...tarjan,SCC,记忆化搜索
[POJ3728]The merchant（tanrjan_lca + DP）
传送门 比着题解写还错。。。 查了两个小时没查出来，心态爆炸啊 以后再查 ——代码（WA） 1 #include cstdio 2 #include cstring 3 #include iostre...DP,lca,tarjan
[luoguP2680] 运输计划（lca + 二分 + 差分）
传送门 暴力做法 50 ~ 60 枚举删边，求最大路径长度的最小值。 其中最大路径长度运用到了lca 我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。 先把边按照权值排序，然...stl,tarjan,lca,dfs,倍增
[luoguP2863] [USACO06JAN]牛的舞会The Cow Prom（Tarjan）
传送门 有向图，找点数大于1的强连通分量个数 ——代码 1 #include stack 2 #include cstdio 3 #include cstring 4 #include iostrea...tarjan,SCC
[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）
传送门 题意 N个点M条边的有向图 每个点有点权 从某一个结点出发 问能获得的最大点权和 一个点的点权最多被计算一次 N=500000 M=500000 思路 先tarjan缩点，然后就形成一个dag...DP,最短路,dfs,spfa,stl
[HDU3062]Party（2-sat）
传送门 2sat问题，只需要判断yes或no 所以可以直接连边，缩点，判断同一组的是否在同一个块中。 1 #include cstdio 2 #include stack 3 #include cst...SCC,tarjan,2-sat
[HAOI2006]受欢迎的牛（tarjan缩点）
洛谷传送门 直接tarjan求scc，然后统计出度为0的缩点，如果多余1个就输出0，只有一个就输出这个缩点里的点。 ——代码 1 #include cstdio 2 #include cstring ...tarjan,SCC
【割点】【割边】tarjan
洛谷割点模板题—— 传送门 割边：在连通图中，删除了连通图的某条边后，图不再连通。这样的边被称为割边，也叫做桥。 割点：在连通图中，删除了连通图的某个点以及与这个点相连的边后，图不再连通。这样的点被称...模板,tarjan,割边,割点
lca最近公共祖先（模板）
洛谷上的lca模板题—— 传送门 1.tarjan求lca 学了求lca的 tarjan算法（离线） ，在洛谷上做模板题，结果后三个点超时。 又把询问改成链式前向星，才ok。 这个 博客 ，tarja...模板,tarjan,倍增,lca,树链剖分
【模板】Tarjan求强连通分量
有人说这篇博客不是很友好，所以我加了点解释，感觉是不是友好多了？ dfn[u]表示节点u在dfs时被访问的次序。 low[u]表示节点u能够追溯到的最远的祖先的dfn。 ins[u]表示节点u是否在栈...模板,tarjan,SCC
共1页/10条
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化