洛谷P4742 [Wind Festival]Running In The Sky [Tarjan缩点,DAGDP]

时间:2022-11-23 19:19:35

  题目传送门

Running In The Sky

格式难调,题面就不放了。


  分析:

  一句话题意:给定一张带点权的有向图,求最长点权路径及该路径上的最大点权。

  很明显的$DAGDP$,因此需要缩点,将该图重建为一张$DAG$,在每个强联通分量中记录两个变量$sum,mx$表示该强联通分量中的点权和及最大点权。然后就是$DP$了,因为不仅要求最长点权路径,还要求路径上的最大点权,所以我们可以记录状态$f[x][0]$和$f[x][1]$分别表示以$x$为终点的路径中点权和最大的路径以及该路径上的最大点权。共有两个方程:

$\begin{cases}f[y][0]=f[x][0],f[y][1]=f[x][1] & (f[x][0]>f[y][0])\\f[y][1]=max(f[y][1],f[x][1]) & (f[x][0]==f[y][0]) \end{cases}$

  这样子这题就很好解决了。

  Code:

//It is made by HolseLee on 26th Oct 2018
//Luogu.org P4742
#include<bits/stdc++.h>
using namespace std; const int N=2e5+, M=5e5+;
int n,m,val[N],ans0,ans1,h[N],head[N],cnte,dg[N],f[N][];
int scc[N],mx[N],sum[N],idx,dfn[N],low[N],tot;
bool ins[N];
struct Edge { int to,nxt; }edge[M],e[M];
queue<int>q; stack<int>t; inline int read()
{
char ch=getchar(); int x=; bool flag=false;
while( ch<'' || ch>'' ) {
if( ch=='-' ) flag=true; ch=getchar(); }
while( ch>='' && ch<='' ) {
x=x*+ch-''; ch=getchar(); }
return flag ? -x : x;
} inline void add_edge(int x,int y)
{
edge[++cnte].to=y;
edge[cnte].nxt=h[x];
h[x]=cnte;
} inline void add(int x,int y)
{
e[++cnte].to=y, e[cnte].nxt=head[x];
head[x]=cnte, dg[y]++;
} void tarjan(int x)
{
dfn[x]=low[x]=++idx; ins[x]=; t.push(x);
int y;
for(int i=h[x]; i; i=edge[i].nxt) {
y=edge[i].to;
if( !dfn[y] ) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if( ins[y] ) {
low[x]=min(low[x],dfn[y]);
}
}
if( dfn[x]==low[x] ) {
++tot;
do {
y=t.top(); t.pop(); ins[y]=false; scc[y]=tot;
sum[tot]+=val[y], mx[tot]=max(mx[tot],val[y]);
} while( y!=x );
}
} void rebuild()
{
cnte=;
for(int x=; x<=n; ++x)
for(int i=h[x],y; i; i=edge[i].nxt) {
y=edge[i].to;
if( scc[x]!=scc[y] ) add(scc[x],scc[y]);
}
} int main()
{
n=read(), m=read();
for(int i=; i<=n; ++i) val[i]=read();
for(int i=; i<=m; ++i) add_edge(read(), read());
for(int i=; i<=n; ++i) if( !dfn[i] ) tarjan(i);
rebuild();
for(int i=; i<=tot; ++i) if( !dg[i] ) q.push(i);
while( !q.empty() ) {
int x=q.front(); q.pop();
f[x][]+=sum[x]; f[x][]=max(f[x][],mx[x]);
for(int i=head[x],y; i; i=e[i].nxt) {
y=e[i].to;
if( !(--dg[y]) ) q.push(y);
if( f[x][]>f[y][] ) {
f[y][]=f[x][], f[y][]=f[x][];
} else if( f[y][]==f[x][] ) {
f[y][]=max(f[y][],f[x][]);
}
}
}
for(int i=; i<=tot; ++i)
if( f[i][]>ans0 ) {
ans0=f[i][], ans1=f[i][];
} else if( f[i][]==ans0 ) {
ans1=max(ans1,f[i][]);
}
printf("%d %d\n",ans0,ans1);
return ;
}