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

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

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

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

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

 

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e3+5;

vectorG[maxn];
int scc,sz[maxn],s[maxn],belong[maxn],top,clk,low[maxn],pre[maxn];

int dfs(int u)
{
    s[++top]=u;
    low[u]=pre[u]=++clk;
    int v;
    for (int i=0; i
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据