tarjan – Tgotp-Blog

P3387 【模板】缩点

把快读里面的0打成了1,

欢笑声中打出gg

先缩点,然后按拓扑序一次求得最大值,不会dag的可以看看

c++代码如下:

 

BZOJ1051 &&P2341 [HAOI2006]受欢迎的牛

tarjan算法,先缩点,然后找出度为零的点就好了.而且出度为零的点只能有一个…

c++代码如下:

 

 

2186 POJ Popular Cows

Popular Cows

Time Limit: 2000MS

Memory Limit: 65536K

Total Submissions: 34191

Accepted: 13925

Description

Every cow’s[……]

Read more

1269 迷宫城堡

Problem Description
为了训练小希的方向感,Gardon建立了一座大城堡,里面有N个房间(N<=10000)和M条通道(M<=100000),每个通道都是单向的,就是说若称某通道连通了A房间和B房间,只说明可以通过这个通道由A房间到达B房间,但并不说明通过它可以由B房[……]

Read more

运输计划BZOJ4326 && P2680 && noip2015T6

算法:tarjan + 二分

思路:先找lca,可以在dfs的时候就用tarjan直接算出,然后找出s -> t的路程,即 q[i].dis = deep[q[i].from] + deep[q[i].to] – 2* deep[q[i].lca];

继续进行二分,对于路程大于假定[……]

Read more