animalcoder

POJ2375题意：给一个n*m，n,m<=500的格子滑雪场，每个格子有个海拔，可以上下左右滑，海拔高的可以滑到海拔低的，海拔相同的可以互相滑现在要建若干电梯（选两个格子使其可以互相到达，无海拔限制）使得从任意一个点出发都可以经过整个滑雪场问最少需要建多少个电梯思路：其实就是问最少加多少条边使得整个图变成强连通图对于缩点后的DAG入度为0 的点的数目 ，出度为0的点的数目之间的较大值就是答...

POJ2762题意：有向图N<=1000 M<=6000，如果图中任意两点u,v 均有u可达v或v可达u，输出YES，否则输出NO思路：嘛，强连通分量内的点肯定互相可达对于缩点之后的DAG，怎么判呢？如果一开始就有多个入度为0的点，那么就是No交一发WA了这时候就要想反例了发现有一种情况也是No比如1 2 ，1 3， 2 4， 3 42 3之间不可达，但是如果把点1跟1的边去掉，就会发...

POJ3160题意：有向图N<=30000,M<=150000，每个点有点权每个点跟路径都能经过多次，到达每个点后可选择进屋，若进屋就获得该点的点权问能获得的最大点权思路：直接跑记忆化，有环，会T，加个vis也不行，因为每个点能经过多次考虑贪心，在一个强连通分量里，能加分的就尽量加分说到强连通我们就会想到tarjan那么我们缩点得到DAG之后跑记忆化就行了DPi表示从i点集出发能获得的...

tarjan有向图求强连通分量学前需知：DFS，前向星，图论知识（强连通，反向边，横边，树边）重点：low的定义，tarjan过程模拟几遍学习链接：http://blog.miskcoo.com/2016/07/tarjan-algorithm-strongly-connected-components例题：poj2553题意：有向图n<=5000，找出所有的sink点，sink点是指sin...