【模板】缩点

洛谷p3387
思路:
算法:tarjan算法

根据题意,我们只要找到一个路径,使得最终权重最大即可,首先,根据题目可知,如果一个点在一个环上,那么我们就将这整个环都选上,题目上允许我们能够重复走,因此,我们可以将环缩成点,将环所称点后,就可以转换成树,从没有父节点的结点开始,我们向下走,每遍历一个子结点,就将子节点更新一次,最终取结点的最大值即可

#include<bits/stdc++.h>using namespace std;int n,m;const int N=1e4+19;const int M=1e5+10;vector<int>vec[N];int a[N];int siz[N];int cnt;int dfn[N],low[N],tot;int p[N];int scc[N];int inDegree[N];stack<int>sta;//tarjan模板  void tarjan(int x){low[x]=dfn[x]=++tot;sta.push(x);for(auto y:vec[x]){if(dfn[y]==0){tarjan(y);low[x]=min(low[x],low[y]);}else if(!scc[y]){low[x]=min(low[x],dfn[y]);}}if(low[x]==dfn[x]){cnt++;while(1){int y=sta.top();sta.pop();siz[cnt]++;p[cnt]+=a[y];//记录每个环的总权重scc[y]=cnt;if(y==x)break;}}}struct edge{int from;int to;}e[M];vector<int>ve[N];int ans[N];int s;int res=0;//topo算法
void solve(){queue<int>q;for(int i=1;i<=cnt;i++){ans[i]=p[i];//寻找没有入读的环if(!inDegree[i])q.push(i);}while(q.empty()==false){int x=q.front();q.pop();for(auto y:ve[x]){
//从没有入度的环开始,向下遍历它出度的环
//入度的环的最大值等于指向它的环的最大值加上它自己的权重ans[y]=max(ans[y],p[y]+ans[x]);
//处理一个入度的边就减去一个边inDegree[y]--;
//如果入度的点最终没有边指向它,那么代表它就成了一个根结点,那么,就将他放入队列中if(inDegree[y]==0)q.push(y);}}for(int i=1;i<=cnt;i++){res=max(res,ans[i]);}cout<<res<<endl;}int main(void){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){int a,b;cin>>a>>b;
//记录边的原因是为了后序我们进行环与环的入度操作时候,可以直接遍历边e[i].from=a;e[i].to=b;vec[a].push_back(b);}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int i=1;i<=m;i++){
//记入环与环之间相连的边int fr=scc[e[i].from];int tr=scc[e[i].to];if(fr==tr)continue;
//记入入度的边inDegree[tr]++;ve[fr].push_back({tr});}solve();}