【模板】縮點https://www.luogu.com.cn/problem/P3387

首先我們要理解這道題為什么要用縮點

題目說的是有向圖，如果無環的話就可以用DP來解決了

由于可以走重復的點，所以一個環上的點可以看成是一個點，它的點權就等于該環上所有點的點權之和，非常符合縮點的作用，所以就可以縮成一個有向無環圖，再用DP解決

強聯通分量

縮點實際上就是找環加DP，找環可以用強聯通分量來解決

具體過程是這樣的：

在遇到環之前一切正常

但當我們回溯到一個點的時候，如果它的low值等于它的dfn值，說明它已經無法與除它的子節點之外的點形成環了，所以我們就遍歷一下之前走過的點，直到遍歷到該節點，此時遍歷到的點就是一個環

強聯通分量代碼：

#include<bits/stdc++.h>
using namespace std;
int n,m,dfn[110000],low[110000],stk[110000],belong[110000],top,tot,cnt;
vector<int>a[110000],ans[110000];
bool vik[110000],instk[110000];
void tarjan(int x)
{dfn[x]=low[x]=++tot;stk[++top]=x;instk[x]=1;for(int i=0;i<a[x].size();i++){if(!dfn[a[x][i]]){tarjan(a[x][i]);low[x]=min(low[x],low[a[x][i]]);//正常tarjan}else if(instk[a[x][i]]) low[x]=min(low[x],dfn[a[x][i]]);}if(low[x]==dfn[x])//找環{int now;cnt++;do{now=stk[top--];ans[cnt].push_back(now);instk[now]=0;belong[now]=cnt;}while(now!=x);}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);if(x==y) continue;a[x].push_back(y);}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);for(int i=1;i<=cnt;i++) sort(ans[i].begin(),ans[i].end());printf("%d\n",cnt);for(int i=1;i<=n;i++){if(vik[i]) continue;int x=belong[i];for(int j=0;j<ans[x].size();vik[ans[x][j++]]=1) printf("%d ",ans[x][j]);printf("\n");}return 0;
}

縮點：

找到環之后，我們就可以將其縮成一個點，然后用拓撲跑DP就可以了，十分簡單

建邊：

for(int i=1;i<=n;i++){for(int j=0;j<a[i].size();j++) {if(belong[i]!=belong[a[i][j]])//如果是不在一個環上{e[belong[i]].push_back(belong[a[i][j]]);//連一條邊}}b[belong[i]]+=c[i];}

完整版：?

#include<bits/stdc++.h>
using namespace std;
int n,m,b[210000],c[210000],dfn[210000],low[210000];
int stk[210000],belong[210000],rd[210000],dp[210000],top,cnt,tot;
vector<int>a[210000],e[210000];
bool instk[210000];
void tarjan(int x)
{low[x]=dfn[x]=++tot;stk[++top]=x;instk[x]=1;for(int i=0;i<a[x].size();i++){if(!dfn[a[x][i]]){tarjan(a[x][i]);low[x]=min(low[x],low[a[x][i]]);}else if(instk[a[x][i]]) low[x]=min(low[x],dfn[a[x][i]]);}if(low[x]==dfn[x]){cnt++;int now;do{now=stk[top--];belong[now]=cnt;instk[now]=0;}while(now!=x);}
}
void topo()
{queue<int>q;while(!q.empty()) q.pop();for(int i=1;i<=cnt;i++) if(!rd[i]) q.push(i);for(int i=1;i<=cnt;i++) dp[i]=b[i];while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<e[x].size();i++){dp[e[x][i]]=max(dp[e[x][i]],dp[x]+b[e[x][i]]);if(--rd[e[x][i]]==0) q.push(e[x][i]);}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&c[i]);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);if(x==y) continue;a[x].push_back(y);}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);for(int i=1;i<=n;i++){for(int j=0;j<a[i].size();j++) {if(belong[i]!=belong[a[i][j]]){e[belong[i]].push_back(belong[a[i][j]]);rd[belong[a[i][j]]]++;}}b[belong[i]]+=c[i];}topo();int ans=0;for(int i=1;i<=cnt;i++) ans=max(ans,dp[i]);printf("%d",ans);return 0;
}