P3387 【模板】缩点

灰太狼 2021-12-10 20:53 262阅读 0赞

题目链接：[https://www.luogu.org/problemnew/show/P3387][https_www.luogu.org_problemnew_show_P3387]

这个题搞了我一天呀；一直以为是dp的问题结果发现是缩点的时候下标打错了~~~

缩完点后，在重建图。在到图上做dp即可。图上dp也是搞了我好久呀。崩溃。

缩点 我是按染色后每个结点的色值缩的点。可以这样想，在重建的图中，每个结点表示一种颜色。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"stack"
    #include"algorithm"
    using namespace std;
    
    int n,m;
    int weight[10010],vis[10010],dfn[10010],low[10010],Stack[10010],color[10010];
    int col_num,color_num[10010];
    int Sweight[10010],visit[10010],in[10010];
    int top,cnt_num,maxxweight;
    vector<int> Q[10010],Graph[10010];
    
    void Tarjan(int x)
    {
        dfn[x] = ++ cnt_num;
        low[x] = cnt_num;
        vis[x] = 1;
        Stack[++ top] = x;
        for(int i = 0; i < Q[x].size(); i ++)
        {
            int v = Q[x][i];
            if(!dfn[v])
            {
                Tarjan(v);
                low[x] = min(low[x],low[v]);
            }
            else if(vis[v])
            {
                low[x] = min(low[x],dfn[v]);
            }
        }
        if(low[x] == dfn[x])
        {
            vis[x] = 0;
            color[x] = ++ col_num;
            Sweight[col_num] = weight[x];
            while(Stack[top] != x)
            {
                vis[Stack[top]] = 0;
                color[Stack[top]] = col_num;
                Sweight[col_num] += weight[Stack[top]];
                top --;
            }
            top --;
        }
    }
    
    int dp[10010];
    
    void dfs(int x)
    {
        if(dp[x] > 0)
            return ;
        dp[x] = Sweight[x];
        int ans = 0;
        for(int i = 0; i < Graph[x].size(); i ++)
        {
            if(!dp[Graph[x][i]])
                dfs(Graph[x][i]);
            ans = max(ans,dp[Graph[x][i]]);
        }
        dp[x] += ans;
        return ;
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i ++)
            scanf("%d",&weight[i]);
        for(int i = 1; i <= m; i ++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            Q[a].push_back(b);
        }
        for(int i = 1; i <= n; i ++)
            if(!dfn[i])
                Tarjan(i);
              //缩点
        for(int i = 1; i <= n; i ++)
            for(int j = 0; j < Q[i].size(); j ++)
            {
                if(color[i] != color[Q[i][j]])
                {
                    Graph[color[i]].push_back(color[Q[i][j]]);
                    in[Q[i][j]] ++;
                }
            }
        int ans = 0;
        //dp最长路
        for(int i = 1; i <= col_num; i ++)
        {
            if(!dp[i])
            {
                dfs(i);
                ans = max(ans,dp[i]);
            }
        }
        printf("%d\n",ans);
    }

[https_www.luogu.org_problemnew_show_P3387]: https://www.luogu.org/problemnew/show/P3387