P3387 【模板】缩点

题目背景

缩点+DP

题目描述

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

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

输入输出格式

输入格式：

第一行，n,m

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

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

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

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

算法：Tarjan缩点+DAGdp

题解：缩点+记忆化搜索

  1 #include<cstdio>
  2 #include <algorithm>
  3 #include <stack>
  4 #include <vector>
  5 #include <cstring>
  6 using namespace std;
  7 
  8 const int MAXN=1e5+10;
  9 const int inf=0x3f3f3f3f;
 10 struct node{
 11     int to;
 12     int next;
 13 }edge[MAXN*4];
 14 int head[MAXN];
 15 int val[MAXN];
 16 bool instack[MAXN];
 17 int cnt;
 18 int dfn[MAXN],low[MAXN];
 19 int sum[MAXN];
 20 void add(int x,int y)
 21 {
 22     edge[++cnt].to =y;
 23     edge[cnt].next=head[x];
 24     head[x]=cnt;
 25 }
 26 int Time,num;
 27 stack<int >st;
 28 vector<int >G[MAXN];
 29 int du[MAXN];
 30 int color[MAXN];
 31 int x[MAXN],y[MAXN];
 32 int f[MAXN];
 33 void search(int x)
 34 {
 35     if(f[x]) return;
 36     f[x]=sum[x];
 37     int maxsum=0;
 38     for (int i = 0; i <G[x].size() ; ++i) {
 39         if(!f[G[x][i]]) search(G[x][i]);
 40         maxsum=max(maxsum,f[G[x][i]]);
 41     }
 42     f[x]+=maxsum;
 43 
 44 }
 45 void tarjan(int u)
 46 {
 47     dfn[u]=low[u]= ++Time;
 48     st.push(u);
 49     instack[u]=true;
 50     for (int i = head[u]; i !=-1 ; i=edge[i].next) {
 51         int v=edge[i].to;
 52         if(!dfn[v]){
 53             tarjan(v);
 54             low[u]=min(low[u],low[v]);
 55         }
 56         else if(instack[v]) low[u]=min(low[u],dfn[v]);
 57     }
 58     if(dfn[u]==low[u])
 59     {
 60         int x;
 61         num++;
 62         while(1) {
 63             x=st.top();
 64             st.pop();
 65             color[x]=num;
 66             instack[x]=false;
 67             if(x==u) break;
 68         }
 69 
 70     }
 71 }
 72 
 73 int main()
 74 {
 75     int n,m;
 76     scanf("%d%d",&n,&m);
 77     for (int i = 1; i <=n ; ++i) {
 78         scanf("%d",&val[i]);
 79     }
 80     cnt=0;
 81     memset(head,-1,sizeof(head));
 82     memset(instack,false, sizeof(instack));
 83     memset(sum, 0,sizeof(sum));
 84     for (int i = 1; i <=m ; ++i) {
 85         scanf("%d%d",&x[i],&y[i]);
 86         add(x[i],y[i]);
 87     }
 88     for (int i = 1; i <=n ; ++i) {
 89         if(!dfn[i]) tarjan(i);
 90     }
 91     for (int i = 1; i <=n ; ++i) {
 92         sum[color[i]]+=val[i];
 93     }
 94     for (int k = 1; k <=num ; ++k) {
 95 //        printf("%d --%d
",k,sum[k]);
 96     }
 97     for (int i = 1; i <=m ; ++i) {
 98         if(color[x[i]]!=color[y[i]])
 99         {
100             G[color[x[i]]].push_back(color[y[i]]);
101         }
102     }
103     for (int i = 1; i <=num; ++i) {
104         for (int j = 0; j <G[i].size() ; ++j) {
105 //            printf("%d-->%d
",i,G[i][j]);
106         }
107     }
108 
109     int ans=0;
110     for (int i = 1; i <=num ; ++i) {
111         if(!f[i]){
112             search(i);
113             ans=max(ans,f[i]);
114         }
115     }
116     printf("%d
",ans);
117     return 0;
118 }