传送门

---

缩点

在一个有向图上缩点就是指把有向图上的环变成一个点。

具体实现用Tarjan。

先求强联通分量，每次遇到新点是把这个点进栈，最后若dfn[i]==low[i]则i这个点一定在环上，而且栈中i之后进入的元素也在这个环上（证明略）。

即一直出栈，知道出栈元素等于i。在出栈过程中维护信息即可。

求完后，枚举原图的每一条边u->v，若u和v不在同一个强联通分量中，则把这两个强联通分量连上边（连点会挂，导致我连续两个晚上疯狂调试）。

曾一度调到12：30，第二天还上课呜呜呜

最后求个dp即可（可以记搜，也可以根据入度用队列求dp）。

AC代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<stack>
 7 using namespace std;
 8 const int maxn=10005;
 9 const int maxm=100005;
10 int scc[10005],num[10005],w[maxn],n,m,p[maxn][2],cnt,times,scc_cnt;
11 int dfn[maxn],low[maxn],dp[maxn],ans;
12 stack<int> s;
13 struct node{
14     int v,next;
15 }e[maxm][2];
16 void insert(int u,int v,int id){
17     cnt++;
18     e[cnt][id].v=v;
19     e[cnt][id].next=p[u][id];
20     p[u][id]=cnt;
21 }
22 void dfs(int u){
23     dfn[u]=low[u]=++times;
24     s.push(u);
25     for(int i=p[u][0];i!=-1;i=e[i][0].next){
26         int v=e[i][0].v;
27         if(dfn[v]==0){
28             dfs(v);
29             low[u]=min(low[u],low[v]);
30         }else if(num[v]==0){
31             low[u]=min(low[u],dfn[v]);
32         }
33     }
34     if(dfn[u]==low[u]){
35         scc_cnt++;
36         while(1){
37             int x=s.top();
38             s.pop();
39             scc[scc_cnt]+=w[x];
40             num[x]=scc_cnt;
41             if(x==u) break; 
42         }
43     }
44 }
45 void dfs2(int u){
46     if(dp[u]) return;
47     dp[u]=max(dp[u],scc[u]);
48     for(int i=p[u][1];i!=-1;i=e[i][1].next){
49         int v=e[i][1].v;
50         dfs2(v);
51         dp[u]=max(dp[u],dp[v]+scc[u]);
52     }
53 }
54 int main()
55 {
56     memset(p,-1,sizeof(p));
57     scanf("%d%d",&n,&m);
58     for(int i=1;i<=n;i++) scanf("%d",&w[i]);
59     for(int i=1;i<=m;i++){
60         int u,v;
61         scanf("%d%d",&u,&v);
62         insert(u,v,0);
63     } 
64     for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
65     cnt=0;
66     for(int u=1;u<=n;u++){
67         for(int i=p[u][0];i!=-1;i=e[i][0].next){
68             int v=e[i][0].v;
69             if(num[u]!=num[v]){
70                 insert(num[u],num[v],1);
71             }
72         }
73     }
74     for(int i=1;i<=scc_cnt;i++){
75         dfs2(i);
76     }
77     for(int i=1;i<=scc_cnt;i++) ans=max(ans,dp[i]);
78     cout<<ans;
79     return 0;
80 }