P3387 【模板】缩点

题目背景

缩点+DP

题目描述

给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入输出格式

输入格式：

 

第一行，n,m

第二行，n个整数，依次代表点权

第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

2 21 11 22 1

输出样例#1： 

2

说明

n<=10^4,m<=10^5,|点权|<=1000 算法：Tarjan缩点+DAGdp

 

啊啊啊啊啊，zz啊，把一个j写成了i，然后调了一晚上、、、

tarjan缩点+spfa求最长路

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 100010using namespace std;queue
          
           q;bool vis[N];int n,m,x,y,tot,tim,top,sum,ans,a[N],v[N],s[N];int dis[N],dfn[N],low[N],head[N],head1[N],stack[N],belong[N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}struct Edge{ int to,next,from;}edge[N],edge1[N];int add(int x,int y){ tot++; edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot;}int add1(int x,int y){ tot++; edge1[tot].to=y; edge1[tot].next=head1[x]; head1[x]=tot;}int spfa(int s){ for(int i=1;i<=n;i++) dis[i]=-1,vis[i]=false; dis[s]=v[s],vis[s]=true; q.push(s),ans=max(ans,v[s]); while(!q.empty()) { x=q.front(); q.pop(),vis[x]=false; for(int i=head1[x];i;i=edge1[i].next) { int t=edge1[i].to; if(dis[t]>dis[x]+v[t]) continue; dis[t]=dis[x]+v[t]; ans=max(ans,dis[t]); if(vis[t]) continue; vis[t]=true,q.push(t); } }}int tarjan(int x){ dfn[x]=low[x]=++tim; stack[++top]=x,vis[x]=true; for(int i=head[x];i;i=edge[i].next) { int t=edge[i].to; if(vis[t]) low[x]=min(low[x],dfn[t]); else if(!dfn[t]) tarjan(t),low[x]=min(low[x],low[t]); } if(low[x]==dfn[x]) { sum++;belong[x]=sum;v[sum]+=a[x]; for(;stack[top]!=x;top--) { v[sum]+=a[stack[top]]; belong[stack[top]]=sum; vis[stack[top]]=false; } vis[x]=false,top--; }}int shink_point(){ tot=0;int t; for(int i=1;i<=n;i++) for(int j=head[i];j;j=edge[j].next) { t=edge[j].to; if(belong[i]!=belong[t]) add1(belong[i],belong[t]); } }int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=m;i++) x=read(),y=read(),add(x,y); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); shink_point(); for(int i=1;i<=sum;i++) spfa(i); printf("%d",ans);}