[强连通分量][DAG][DP] UVa11324

算是学到了缩点构造新图的方法吧emm有点笨

有环的图一般都有点难倒腾,所以这种都是遇见了先求scc,变成DAG以后再想办法求解。

分析题意后可以发现,对于DAG,求出来的其实是一条路径,因为如果有分叉的话分叉的不同子树之间就没有办法互通了。令每个缩点的权值为含点的个数,这样就转化成了DAG上的最长路问题了。

错误:scc每次都会出现漏初始化错误。。。还有就是缩点之后的节点标记与原来的节点意义不同,要注意。

  继续阅读“[强连通分量][DAG][DP] UVa11324”