\(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;
}