Luogu3387 缩点

题目背景

缩点+DP

题目描述

给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式：

第一行，n,m

第二行，n个整数，依次代表点权

第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

输出格式：

共一行，最大的点权之和。

输入样例：

2 2

1 1

1 2

2 1

输出样例：

说明

n<=10^4,m<=10^5,点权<=1000

挺板子的一道题，敲它主要是因为最近爱上了封装科技

虽然题面没有说，不过这道题的数据好像没有涉及到负数，不然还有点麻烦

直接把原图tarjan缩点然后DAG上面DP就好了

小技巧：如果不想考虑缩点之后两个点之间有多条边的情况，直接记忆化搜索就好了

//yangkai

#include<bits/stdc++.h>

using namespace std;

#define N 100010

int m,ans=0,ru[N],f[N];

struct Edge{int u,v,next;};

struct G{

    Edge E[N];

    int head[N],val[N],tot,siz;//siz:节点个数

    G(){

        tot=0;

        memset(head,0,sizeof(head));

        memset(val,0,sizeof(val));

    }

    void add(int u,int v){

        E[++tot]=(Edge){u,v,head[u]};

        head[u]=tot;

    }

}g1,g2;

struct Tarjan{

    G g;

    int dfn[N],low[N],belong[N],index,cnt;

    bool vis[N];

    stack<int> s;

    Tarjan(){index=cnt=0;}

    void tarjan(int u){

        vis[u]=1;s.push(u);

        dfn[u]=low[u]=++index;

        for(int i=g.head[u];i;i=g.E[i].next){

            int v=g.E[i].v;

            if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);

            else if(vis[v])low[u]=min(low[u],dfn[v]);

        }

        if(low[u]==dfn[u]){

            int v;cnt++;

            do{

                v=s.top();s.pop();

                belong[v]=cnt;

                vis[v]=0;

            }while(v!=u);

        }

    }

    void tarjan(){

        for(int i=1;i<=g.siz;i++)

            if(!dfn[i])tarjan(i);

    }

}tar;

int dfs(int u){//记忆化搜索部分

    if(f[u])return f[u];

    for(int i=g2.head[u];i;i=g2.E[i].next){

        int v=g2.E[i].v;

        f[u]=max(f[u],dfs(v));

    }

    return f[u]+=g2.val[u];

}

int main(){

    scanf("%d%d",&g1.siz,&m);

    for(int i=1;i<=g1.siz;i++)scanf("%d",&g1.val[i]);

    for(int i=1;i<=m;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        g1.add(u,v);

    }

    tar.g=g1;

    tar.tarjan();

    for(int i=1;i<=g1.siz;i++)

    g2.siz=tar.cnt;

    for(int i=1;i<=g1.siz;i++)g2.val[tar.belong[i]]+=g1.val[i];

    for(int i=1;i<=m;i++)if(tar.belong[g1.E[i].u]!=tar.belong[g1.E[i].v])

        g2.add(tar.belong[g1.E[i].u],tar.belong[g1.E[i].v]),ru[tar.belong[g1.E[i].v]]=1;

    for(int i=1;i<=g2.siz;i++)if(!ru[i])ans=max(ans,dfs(i));//考虑可能有多个入入度为0的点

    printf("%d\n",ans);

    return 0;

}

巴特西

Luogu3387 缩点【tarjan】【DP】

Luogu3387 缩点

题目背景

题目描述

输入格式：

输出格式：

输入样例：

输出样例：

说明

最新文章

热门文章

巴特西

Luogu3387 缩点 【tarjan】【DP】

Luogu3387 缩点

题目背景

题目描述

输入格式：

输出格式：

输入样例：

输出样例：

说明

最新文章

热门文章

Luogu3387 缩点【tarjan】【DP】