[洛谷P1262]间谍网络[tarjan缩点]

题面
tarjan缩点模板题

tj的思路: 强连通分量可以相互到达, 必定在一个环上, 一次dfs找出所有尽量大的环即可.

sta里面是表示当前所有可能能构成强连通分量的点, 追溯值low[x]表示点x及其子孙节点连的所有点中dfn的最小值, 如果遇到环就会发现不能再往下搜, 接着会一直回溯至进入环的点x(low[x]=dfn[x], 途中要从后往前维护所有点的low), 这时弹掉栈中这个环上的所有点即可.

记得图可能不连通, 要尝试从每个点开始做tj. 缩点建新图可以枚举每个点然后看此点与哪些点之间有边, 若两点右边且不再同一强连通分量中就在新图上连边. 注意区分旧图新图!
对于本题, 每个强连通分量收买最便宜的那个即控制了整个分量
所以缩点后收买所有入度为0的点即可
若不能收买则无解

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址