P3387 【模板】缩点
题目背景
缩点+DP
题目描述
给定一个n个点m条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。
输入输出格式
输入格式:
第一行,n,m
第二行,n个整数,依次代表点权
第三至m+2行,每行两个整数u,v,表示u->v有一条有向边
输出格式:
共一行,最大的点权之和。
输入输出样例
输入样例#1: 复制
2 2
1 1
1 2
2 1
输出样例#1: 复制
2
说明
n<=10^4,m<=10^5,|点权|<=1000 算法:Tarjan缩点+DAGdp
做法
缩点
然后就变成了一个DAG问题
花了很长时间调Tarjan
大概有1.5h
然后根据拓扑序更新答案
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 100005
using namespace std;
inline void read(int &s){
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(s=0;isdigit(ch);s=s*10+ch-'0',ch=getchar());
}
struct Edge{
int /*u,*/v,nxt;
}e[N],E[N];
int head[N],tot;
int h[N],num;
int n,m;
int v[N];
int V[N];
int du[N];
int col_num;
int cost[N];
int stack[N];
int top,dfn_tim;
int dfn[N],col[N];
int low[N],vis[N];
void addEdge(int a,int b){
e[++tot].v=b;
e[tot].nxt=head[a];
head[a]=tot;
}
void AddEdge(int a,int b){
du[b]++;
E[++num].v=b;
E[num].nxt=h[a];
h[a]=num;
}
void Tarjan(int x){
dfn[x]=low[x]=++dfn_tim;
stack[++top]=x;
vis[x]=true;
for(int i=head[x];i;i=e[i].nxt){
int to=e[i].v;
if(!dfn[to]){
Tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(vis[to])low[x]=min(low[x],dfn[to]);
}
if(low[x]==dfn[x]){
++col_num;
vis[x]=false;
col[x]=col_num;
V[col_num]+=v[x];
while(stack[top]!=x){
col[stack[top]]=col_num;
V[col_num]+=v[stack[top]];
vis[stack[top]]=false;
--top;
}
top--;
}
}
int que[N],dp[N];
int DAGTopsort(){
int H=0,T=0,top,ans=0;
for(int i=1;i<=col_num;++i)
if(!du[i]){
que[++T]=i;
dp[i]=V[i];
ans=max(dp[i],ans);
}
while(H<T){
top=que[++H];
for(int i=h[top];i;i=E[i].nxt){
int to=E[i].v;
du[to]--;
dp[to]=max(dp[to],dp[top]+V[to]);
ans=max(ans,dp[to]);
if(!du[to])
que[++T]=to;
}
}
return ans;
}
int main(){
int a,b;
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;++i)
read(v[i]);
for(int i=1;i<=m;++i){
read(a),read(b);
addEdge(a,b);
}
stack[0]=0;
for(int i=1;i<=n;++i)
if(!dfn[i])
Tarjan(i);
for(int i=1;i<=n;++i)
for(int j=head[i];j;j=e[j].nxt)
if(col[i]!=col[e[j].v]){
AddEdge(col[i],col[e[j].v]);
}
printf("%d
",DAGTopsort());
}
return 0;
}