Luogu3387 缩点
题目背景
缩点+DP
题目描述
给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入格式：
第一行，n,m
第二行，n个整数，依次代表点权
第三至m+2行，每行两个整数u,v，表示u->v有一条有向边
输出格式：
共一行，最大的点权之和。
输入样例：
2 2
1 1
1 2
2 1
输出样例：
2
说明
n<=10^4,m<=10^5,点权<=1000
挺板子的一道题，敲它主要是因为最近爱上了封装科技
虽然题面没有说，不过这道题的数据好像没有涉及到负数，不然还有点麻烦
直接把原图tarjan缩点然后DAG上面DP就好了
小技巧：如果不想考虑缩点之后两个点之间有多条边的情况，直接记忆化搜索就好了
//yangkai
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int m,ans=0,ru[N],f[N];
struct Edge{int u,v,next;};
struct G{
Edge E[N];
int head[N],val[N],tot,siz;//siz:节点个数
G(){
tot=0;
memset(head,0,sizeof(head));
memset(val,0,sizeof(val));
}
void add(int u,int v){
E[++tot]=(Edge){u,v,head[u]};
head[u]=tot;
}
}g1,g2;
struct Tarjan{
G g;
int dfn[N],low[N],belong[N],index,cnt;
bool vis[N];
stack<int> s;
Tarjan(){index=cnt=0;}
void tarjan(int u){
vis[u]=1;s.push(u);
dfn[u]=low[u]=++index;
for(int i=g.head[u];i;i=g.E[i].next){
int v=g.E[i].v;
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
int v;cnt++;
do{
v=s.top();s.pop();
belong[v]=cnt;
vis[v]=0;
}while(v!=u);
}
}
void tarjan(){
for(int i=1;i<=g.siz;i++)
if(!dfn[i])tarjan(i);
}
}tar;
int dfs(int u){//记忆化搜索部分
if(f[u])return f[u];
for(int i=g2.head[u];i;i=g2.E[i].next){
int v=g2.E[i].v;
f[u]=max(f[u],dfs(v));
}
return f[u]+=g2.val[u];
}
int main(){
scanf("%d%d",&g1.siz,&m);
for(int i=1;i<=g1.siz;i++)scanf("%d",&g1.val[i]);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
g1.add(u,v);
}
tar.g=g1;
tar.tarjan();
for(int i=1;i<=g1.siz;i++)
g2.siz=tar.cnt;
for(int i=1;i<=g1.siz;i++)g2.val[tar.belong[i]]+=g1.val[i];
for(int i=1;i<=m;i++)if(tar.belong[g1.E[i].u]!=tar.belong[g1.E[i].v])
g2.add(tar.belong[g1.E[i].u],tar.belong[g1.E[i].v]),ru[tar.belong[g1.E[i].v]]=1;
for(int i=1;i<=g2.siz;i++)if(!ru[i])ans=max(ans,dfs(i));//考虑可能有多个入入度为0的点
printf("%d
",ans);
return 0;
}