【-73】P3387 【模板】缩点[tarjan+DAGdp]

题目描述

给定一个n个点m条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。

输入输出格式

输入格式:

第一行,$n,m$
第二行,$n$ 个整数,依次代表点权
第三至 $m+2$ 行,每行两个整数 $u$,$v$,表示 $u->v$ 有一条有向边

输出格式:

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

输入输出样例

输入样例#1:

2 2
1 1
1 2
2 1

输出样例#1:

2

说明

$n\le10^4,m\le10^5,|点权|\le1000$ 算法:Tarjan缩点+DAGdp

题解

缩点+DAGdp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9') {k=k*10+(s-'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0) {putchar('-');write(-x);}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=101000;
const int maxm=2001000;
int pre[maxn],low[maxn],dis[maxn],Dis[maxn],dp[maxn];
int to[maxm],ne[maxm],po[maxn],d;
int To[maxm],Ne[maxm],Po[maxn],D;
int rd[maxn];
int scc[maxn],id;
int n,m,X[maxm],Y[maxm];
int dfs_clock;
stack<int> S;
queue<int> Q;
inline void add(int x,int y)
{
d++;
to[d]=y;ne[d]=po[x];po[x]=d;
}
inline void Add(int x,int y)
{
D++;
To[D]=y;Ne[D]=Po[x];Po[x]=D;//Ne[D]的D打成小写了
}
inline void dfs(int x)//缩点
{
++dfs_clock;//时间戳
pre[x]=dfs_clock;//记录自己的时间
low[x]=pre[x];
S.push(x);
for (int i=po[x];i;i=ne[i])//一条一条边的搞
{
int y=to[i];
if (pre[y]==0)
{//没扫过就扫
dfs(y);
low[x]=min(low[x],low[y]);//更新
} else
if (scc[y]==0) low[x]=min(low[x],pre[y]);//不属于任何一个scc就更新
}
if (low[x]==pre[x])//开始pre[x]打成x了2333
{//如果搜不到比自己更早的点了
id++;//scc增加
while (true)
{
int u=S.top();S.pop();
scc[u]=id;//标记
Dis[id]+=dis[u];//点权加起来
if (u==x) break;
}
}
}
int main()
{
n=read();m=read();
for (int i=1;i<=n;i++) dis[i]=read();
for (int i=1;i<=m;i++)
{
X[i]=read();Y[i]=read();add(X[i],Y[i]);
}
for (int i=1;i<=n;i++) if (pre[i]==0) dfs(i);
for (int i=1;i<=m;i++)
{
if (scc[X[i]]!=scc[Y[i]])//重新建图
{
Add(scc[X[i]],scc[Y[i]]);
rd[scc[Y[i]]]++;//记入度
}
}
int ans=0;
for (int i=1;i<=id;i++)//入度为0的点入队
{
dp[i]=Dis[i];
ans=max(ans,Dis[i]);
if (rd[i]==0) Q.push(i);
}
while (!Q.empty())
{
int u=Q.front();Q.pop();
for (int i=Po[u];i;i=Ne[i])
{
int v=To[i];
dp[v]=max(dp[v],dp[u]+Dis[v]);//求max
ans=max(ans,dp[v]);//更新ans
rd[v]--;
if (rd[v]==0) Q.push(v);//入度为0就入队
}
}
printf("%d",ans);
return 0;
}