/目录1问题描述2解决方案   引用自百度百科： 如果两个顶点可以相互通达，则称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(stronglyconnectedcom...

/目录1问题描述2解决方案 ProblemDescription为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过...

大佬博客：here                模板题目：P4782【模板】2-SAT问题  AC_Code:1#include<b...

 在有向图G中，如果两点互相可达，则称这两个点强连通，如果G中任意两点互相可达，则称G是强连通图。定理：1、一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。      2、非强连通有向图的极大强连通子图，称为强连通分量（SCC即...

/**题目大意:给你一个无向连通图,问加上一条边后得到的图的最少的割边数;算法思想:图的边双连通Tarjan算法+树形DP;即通过Tarjan算法对边双连通缩图,构成一棵树,然后用树形DP求最长链,连接首尾即可;剩下的连通块即为所求答案;算法思路:对图深度优先搜索,定义DFN(u)为u在搜索树中被遍历到的次序号;定义L...

　　有一个有向图，每一个节点有一个权值，其中有一些结束点。　　现在，你要从S出发，到达任意一个结束点，使得经过的节点的权值和最大（可以重复经过某一个节点，但是权值只记入一次）。 　　小码农题。　　如果有强连通分量，那么之间的点是可以全部拿到的，傻子才不拿。　　所以先Tarjan强连通缩个点。　　然后就是一个D...

 　　有n只牛，有m个羡慕关系。　　羡慕关系具有传递性。　　如果A羡慕B，B羡慕C，那么我们认为A也羡慕C。　　问有多少牛被所有其他牛羡慕。 　　这次做这题我已经是第三遍了。　　USACO经典老题啊！（奶牛）　　POJ上面也有，叫popularcow。　　做法：　　先Tarjan强连通缩个点。　　然...

原文链接http://www.cnblogs.com/zhouzhendong/p/7256007.html UPD(2018-5-13):细节修改以及使用了Latex代码，公式更加美观。改的过程中发现许多叙述上的问题，已经修改。然而得到这么多阅读量我真的是受宠若惊。于是我决定再补写一个在线$O(1)$查询的...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ290.html真是一道好题！首先，如果不是仙人掌直接输出0。否则，显然先把环上的边删光。问题转化成多个树求解，把答案乘起来即可。现在我们考虑如何求一个树的答案。再转化一下题意可以变成选出若干条长度至少为2的路径使得它们两两没有...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ23.html　　给定一个有n个节点的仙人掌（可能有重边）。　　对于所有的$L(1leqLleqn-1)$，求出有多少不同的从节点1出发的包含L条边的简单路径。简单路径是指不重复经过任意一点。　　$nleq10^5$　　首先我们...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF980F.html　　给定一个$n$个节点$m$条长为$1$的边的每个点最多只属于一个环的仙人掌。　　现在请你通过删边把仙人掌转化成树。　　对于每一个点，输出在所有不同的删边方案中， 距离该点最远的点与他之间的距离值的最...

原文链接https://www.cnblogs.com/zhouzhendong/p/9258043.html　　给定一个有向图，有$n$个节点$m$条边，边权值$in[0,1000]$。　　小明要从$1$走到$n$，要求路径长度最大为$d+k$，其中$d$为$1$到$n$最短路长度。　　问小明有多少种走法，答案对$p...

Tarjan基础　　dfn[i]:在dfs中该节点被搜索的次序(时间戳)。　　low[i]:为i或i的子树能够追溯到的最早的栈中节点的次序号。　　当 dfn[i]==low[i] 时，为i或i的子树可以构成一个强连通分量。voidtarjan(intx){id++;dfn[x]=id;low[x]=...

迷宫城堡TimeLimit:2000/1000MS(Java/Others)   MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):21627   AcceptedSubmission(s):941...