LGOJ P3387 【模板】缩点

\(Tarjan\)模板....

题目背景

缩点+DP

题目描述

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

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

输入格式

第一行，n,m

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

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

输出格式

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

输入输出样例

输入 #1
2 2
1 1
1 2
2 1
输出 #1
2

说明/提示

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

算法：Tarjan缩点+DAGdp

#include <bits/stdc++.h>
using namespace std;
const int N=10005,INF=0x3f3f3f3f;
int PW[N],DFN[N],LOW[N],n,m,ts,COL[N],cc,WT[N];
vector<int>G[N];
int g[N][N];
stack<int> S;
bool in[N];
inline int read()
{
    int x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(; isdigit(c);c=getchar())
        x=x*10+c-'0';
    return x;
}

void Tarjan(int u)
{
//  cout<<"Dsd"<<endl;
    LOW[u]=DFN[u]=++ts;
    S.push(u);
    in[u]=1;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(!DFN[v])
        {
            Tarjan(v);
            LOW[u]=min(LOW[u],LOW[v]);
        }
        else if(in[v])
        {
            LOW[u]=min(DFN[v],LOW[u]);
        }
    }
    if(DFN[u]==LOW[u])
    {
        cc++;
        while(1)
        {
            int x=S.top();
            S.pop();
            in[x]=0;

            COL[x]=cc;
            WT[cc]+=PW[x];

            //
        //  cout<<"IDD"<<x<<endl;

            if(x==u)break;
        }
    }
}

int f[N];
int dp(int u)
{
//  cout<<"DP:f"<<u<<"   "<<endl;
    if(f[u])return f[u];
    f[u]=WT[u];
    for(int i=1;i<=cc;i++)
    {
        if(g[u][i])
        {
            f[u]=max(f[u],dp(i)+WT[u]);
        //  cout<<"INS"<<endl;
        }
    }
    return f[u];
}



int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)PW[i]=read();
    for(int i=1;i<=m;i++)
    {
        int u=read();
        int v=read();
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++)if(!DFN[i])Tarjan(i);

//  cout<<COL[1]<<" "<<COL[2]<<endl;

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<G[i].size();j++)
        {
            int u=i,v=G[i][j];
            if(COL[u]!=COL[v])
            {
                g[COL[u]][COL[v]]=1;
            }
        }
    }

    int maxx=0;
    for(int i=1;i<=cc;i++)maxx=max(maxx,dp(i));
    cout<<maxx;

    return 0;
}