zcmimi's blog

arrow_backtarjan共19篇文章

avatar
zc
2019-12-31 22:54:00
查看原题

点击跳转

夫妻之间:girl \to boy

情人之间:boy \to girl

Tarjan求强连通分量,对于一对夫妻,如果两人在同一个强连通分量里,那么这对婚姻就是不安全的,反之,则是安全的。

avatar
zc
2019-12-31 21:29:00
查看原题

点击跳转

假设当前被封锁的是x

如果x不是割点,那么除x外的点都连通,答案为2\times(n-1)(x和其他n-1个点配对)

如果x是割点,删掉x后图会变成若干个连通块,设这些连通块大小为t_1,t_2,...,t_a

那么答案为:\sum_{i=1}^a t_i\times(n-t_i)+(1+sum)\times(n-sum-1)+n-1

avatar
zc
2019-12-31 20:01:00
查看原题

点击跳转

分类讨论:

Tarjan跑出割点,然后DFS搜索所有的联通快

计算每一个联通快中的割点数目

分类讨论:

  1. 没有割点

    至少需要建立两个出口

    从任意非割点的地方选择两个点建立

  2. 这个分组只有一个割点

    只需要在分组内设立一个出口

    可以设立在任意一个非割点的地方

  3. 有两个及以上个割点,则无需建立,可以直接到达其他联通块

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

因为有两条不同的路径,而且没有重边,所以这两个点就在同一个强连通分量里,直接tarjan一遍就可以

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

tarjan找出强连通分量之后树形dp

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

缩点后跑最长路

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先缩点,然后跑最长路

然后更新的时候顺便记录最大亮度就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

tarjan找出环 答案是每个环上的最小值加起来

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Fake-tournament top: 0

tarjan强连通分量缩点一下

最多只有一个入度为0的点,

否则就是没有符合条件的点

2/2
Search
search