洛谷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

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 using namespace std;
  7 long long read()
  8 {
  9     long long x=0,f=1;
 10     char ch=getchar();
 11     while(ch<'0'||ch>'9')
 12     {
 13         if(ch=='-')
 14             f=-1;
 15         ch=getchar();
 16     }
 17     while(ch>='0'&&ch<='9')
 18     {
 19         x=x*10+ch-'0';
 20         ch=getchar();
 21     }
 22     return x*f;
 23 }
 24 void write(long long x)
 25 {
 26     if(x<0)
 27     {
 28         x=-x;
 29         putchar('-');
 30     }
 31     if(x>9)
 32         write(x/10);
 33     putchar(x%10+'0');
 34 }
 35 const int maxn=10005;
 36 const int maxm=100005;
 37 struct node
 38 {
 39     int v,u,nxt;
 40 } e[maxm*50];
 41 int rudu[maxn],head[maxn],dfn[maxn],low[maxn],sta[maxn],dp[maxn],w[maxn],ww[maxn],fa[maxn];
 42 bool vis[maxn];
 43 queue<int>q;
 44 int n,m,num,top,ans,tot,cnt;
 45 void add(int u,int v)
 46 {
 47     e[++num].v=v;
 48     e[num].u=u;
 49     e[num].nxt=head[u];
 50     head[u]=num;
 51 }
 52 void tarjan(int x)
 53 {
 54     cnt++;
 55     dfn[x]=low[x]=cnt;
 56     vis[x]=1;
 57     top++;
 58     sta[top]=x;
 59     for(int i=head[x]; i; i=e[i].nxt)
 60     {
 61         int v=e[i].v;
 62         if(dfn[v]==0)
 63         {
 64             tarjan(v);
 65             low[x]=min(low[x],low[v]);
 66         }
 67         else if(vis[v])
 68             low[x]=min(low[x],low[v]);
 69     }
 70     if(low[x]==dfn[x])
 71     {
 72         tot++;
 73         while(sta[top]!=x)
 74         {
 75             fa[sta[top]]=tot;
 76             ww[tot]+=w[sta[top]];
 77             vis[sta[top]]=0;
 78             top--;
 79         }
 80         fa[sta[top]]=tot;
 81         ww[tot]+=w[sta[top]];
 82         vis[sta[top]]=0;
 83         top--;
 84     }
 85     return ;
 86 }
 87 int main()
 88 {
 89     n=read(),m=read();
 90     for(int i=1; i<=n; i++)
 91         w[i]=read();
 92     for(int i=1; i<=m; i++)
 93     {
 94         int u,v;
 95         u=read(),v=read();
 96         add(u,v);
 97     }
 98     for(int i=1; i<=n; i++)
 99         if(dfn[i]==0)
100             tarjan(i);
101     memset(head,0,sizeof head);
102     for(int i=1; i<=m; i++)
103     {
104         int u,v;
105         u=fa[e[i].u],v=fa[e[i].v];
106         if(u!=v)
107         {
108             add(u,v);
109             rudu[v]++;
110         }
111     }
112     for(int i=1; i<=tot; i++)
113     {
114         ans=max(ans,ww[i]);
115         if(rudu[i]==0)
116         {
117             q.push(i);
118             dp[i]+=ww[i];
119         }
120     }
121     while(!q.empty())
122     {
123         int now=q.front();
124         q.pop();
125         for(int i=head[now]; i; i=e[i].nxt)
126         {
127             int v=e[i].v;
128             dp[v]=max(dp[v],dp[now]+ww[v]);
129             ans=max(ans,dp[v]);
130             rudu[v]--;
131             if(rudu[v]==0)
132                 q.push(v);
133         }
134     }
135     write(ans);
136     return 0;
137 }

View Code