文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P3387
D
e
s
c
r
i
p
t
i
o
n
Description
Description
给定一张
n
n
n个点，
m
m
m条边的有向图，点有点权 找出一条路径使得经过的点的权值和最大，点和边可以重复经过，但是只算一次贡献
数据范围：
n
≤
1
0
4
,
m
≤
1
0
5
n\leq 10^4,m\leq 10^5
n≤104,m≤105
S
o
l
u
t
i
o
n
Solution
Solution
容易发现每个环如果选的话，这个环都会直接选掉，所以我们可以把每个环缩成一个点，它的点权就重新定义成所有点的取值和
接下来就是一个简单的
D
A
G
d
p
DAGdp
DAGdp了，设
f
i
f_i
fi表示以
i
i
i为终点的最大路径和，显然有
f
j
=
m
a
x
{
f
i
}
+
v
j
f_j=max\{f_i\}+v_j
fj=max{fi}+vj，按照拓扑序转移即可
时间复杂度：
O
(
n
+
m
)
O(n+m)
O(n+m)
C
o
d
e
Code
Code
#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10010
#define M 200010
#define LL long long
using namespace std
;int n
,m
,v
[N
],le
[N
],lg
[N
],tote
,totg
,a
,b
,rd
[N
],f
[N
];
struct node
{int next
,to
;}e
[M
],g
[M
];
inline void adde(int u
,int v
){e
[++tote
]=(node
){le
[u
],v
};le
[u
]=tote
;return;}
inline void addg(int u
,int v
){g
[++totg
]=(node
){lg
[u
],v
};lg
[u
]=totg
;return;}
bool vis
[N
];
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
int low
[N
],dfn
[N
],stk
[N
],top
,cnt
,which
[N
];
inline void Tarjan(int x
)
{
low
[x
]=dfn
[x
]=++cnt
;
stk
[++top
]=x
;vis
[x
]=true;
for(register int i
=le
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(dfn
[y
]==0)
{
Tarjan(y
);
low
[x
]=min(low
[x
],low
[y
]);
}
else if(vis
[y
]) low
[x
]=min(low
[x
],dfn
[y
]);
}
if(dfn
[x
]==low
[x
])
{
int y
;
while(y
=stk
[top
--])
{
which
[y
]=x
;vis
[y
]=false;
if(x
==y
) break;
v
[x
]+=v
[y
];
}
return;
}
}
signed main()
{
n
=read();m
=read();
for(register int i
=1;i
<=n
;i
++) v
[i
]=read();
for(register int i
=1;i
<=m
;i
++) a
=read(),b
=read(),adde(a
,b
);
for(register int i
=1;i
<=n
;i
++) if(!dfn
[i
]) Tarjan(i
);
for(register int x
=1;x
<=n
;x
++)
for(register int i
=le
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(which
[x
]!=which
[y
]) addg(which
[x
],which
[y
]),rd
[which
[y
]]++;
}
queue
<int>q
;
for(register int i
=1;i
<=n
;i
++) if(which
[i
]==i
&&rd
[i
]==0) q
.push(i
),f
[i
]=v
[i
];
while(q
.size())
{
int x
=q
.front();q
.pop();
for(register int i
=lg
[x
];i
;i
=g
[i
].next
)
{
int y
=g
[i
].to
;
f
[y
]=max(f
[y
],f
[x
]+v
[y
]);
if(--rd
[y
]==0) q
.push(y
);
}
}
int res
=0;
for(register int i
=1;i
<=n
;i
++) res
=max(res
,f
[i
]);
printf("%d",res
);
}
