洛谷 P3387 【模板】缩点
题目

分析

代码

题目背景

缩点+DP

题目描述

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

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

输入格式

第一行，n,m

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

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

输出格式

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

输入输出样例

输入 #1

输出 #1

说明/提示

n<=10^4,m<=10^5,0<=点权<=1000

算法：Tarjan缩点+DAGdp

分析

tarjan模板，因为经过点可以重复，但是权值只能纪录一次
那么我们将环缩成一个点
然后直接跑记忆化
找到最大值就好了

代码

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 struct sb
 5 {
 6     int to,nx;
 7 }g[200001];
 8 int x[100001],y[100001],t[100001];
 9 int cnt,list[200001];
10 void add(int x,int y)
11 {
12     g[++cnt].to=y; g[cnt].nx=list[x]; list[x]=cnt;
13 }
14 int dfn[100001],low[100001],num,stack[100010],top,color[100010],col,sum[100010],vis[100010];
15 void tarjan(int x)
16 {
17     dfn[x]=++num;
18     low[x]=num;
19     vis[x]=1;
20     stack[++top]=x;
21     for (int i=list[x];i;i=g[i].nx)
22     {
23         int y=g[i].to;
24         if (!dfn[y])
25         {
26             tarjan(y);
27             low[x]=min(low[x],low[y]);
28         }
29         else if (vis[y]) low[x]=min(low[x],dfn[y]);
30     }
31     if (dfn[x]==low[x]) 
32     {
33         ++col;
34         while (stack[top+1]!=x)
35         {
36             color[stack[top]]=col;
37             sum[col]+=t[stack[top]];
38             vis[stack[top--]]=false;
39         }
40     }
41 }
42 int f[100010];
43 void dfs(int x)
44 {
45     if (f[x]) return;
46     f[x]=sum[x];
47     int maxsum=0;
48     for (int i=list[x];i;i=g[i].nx)
49     {
50         int y=g[i].to;
51         if (!f[y]) dfs(y);
52         maxsum=max(maxsum,f[y]);
53     }
54     f[x]+=maxsum;
55 }
56 int main ()
57 {
58     int n,m;
59     cin>>n>>m;
60     for (int i=1;i<=n;i++) cin>>t[i];
61     for (int i=1;i<=m;i++)
62     {
63         cin>>x[i]>>y[i];
64         add(x[i],y[i]);
65     }
66     for (int i=1;i<=n;i++)
67       if (!dfn[i]) tarjan(i);
68     memset(g,0,sizeof(g));
69     memset(list,0,sizeof(list));
70     cnt=0;
71     for (int i=1;i<=m;i++)
72        if (color[x[i]]!=color[y[i]])
73          add(color[x[i]],color[y[i]]);
74     int ans=0;
75     for (int i=1;i<=col;i++)
76       if (!f[i])
77       {
78            dfs(i);
79            ans=max(ans,f[i]);
80       }
81     cout<<ans;
82     
83 }

洛谷 P3387 【模板】缩点 题目 分析 代码