动态网站开发的集成网站/安卓aso优化排名

可以多次走一个点或一条边，但只计算一次点权，意味着我们需要进行缩点

tarjan进行求强联通分量主要记录DFN[i],LOW[i]，以及维护que记录走过的点

通过后向边和树枝边对LOW值的更新，当DFN[i]=LOW[i]时，就出现了强连通分量，可以进行缩点操作

在缩点后，重新建图，然后就可以通过dp（记忆化） 进行统计

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxm=1e5+5;
int n,m,tot,inin[maxn],dp[maxn],ans,color[maxn],va[maxn],LOW[maxn],times,top,cnt,que[maxn],DFN[maxn],head[maxn],val[maxn],ux[maxm],uy[maxm];
struct edge
{int to,nxt;
}G[maxm<<1];
void add(int x, int y)
{G[++cnt].to=y; G[cnt].nxt=head[x]; head[x]=cnt;
}
void tarjan(int x)
{que[++top]=x;inin[x]=1;DFN[x]=LOW[x]=++times;for(int i=head[x];i;i=G[i].nxt){int to=G[i].to;if(!DFN[to]) {tarjan(to);LOW[x]=min(LOW[x],LOW[to]);}else if(inin[to])LOW[x]=min(LOW[x],DFN[to]);}if(DFN[x]==LOW[x]){tot++;while(que[top+1]!=x){color[que[top]]=tot;va[tot]+=val[que[top]];inin[que[top--]]=0;}}
}
void dpp(int x)
{if(dp[x]) return ;dp[x]=va[x];int maxsum=0;for(int i=head[x];i;i=G[i].nxt){int to=G[i].to;if(!dp[to]) dpp(to);maxsum=max(maxsum,dp[to]);}dp[x]+=maxsum;
}
int main()
{freopen("a.in","r",stdin);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&val[i]);for(int i=1;i<=m;i++){scanf("%d%d",&ux[i],&uy[i]);add(ux[i],uy[i]);}for(int i=1;i<=n;i++)if(!DFN[i]) tarjan(i);memset(head,0,sizeof(head));cnt=0;for(int i=1;i<=m;i++)if(color[ux[i]]!=color[uy[i]])add(color[ux[i]],color[uy[i]]);for(int i=1;i<=tot;i++){if(!dp[i]){dpp(i);ans=max(ans,dp[i]);}}printf("%d\n",ans);return 0;
}