先科普一下简写,DAG指的是有向连通图,SCC指的是强连通分量。

例题:洛谷 P3387 【模板】缩点

思路就是用Tarjan算法或者Kosaraju算法求强连通分量,然后把每个强连通分量变成一个点,重新建图,图就变成了DAG,用拓扑排序进行dp即可。

tarjan文章 洛谷博文

一、Tarjan算法

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5+10;
int n,m,x[N],y[N];
int scc[N]; // 每个点属于的连通块
int cnt; // 连通块个数
int tim; // dfs序时间戳
int dfn[N]; // 存每个点的dfs序
int low[N]; // 存每个点属于的scc的祖先(每个scc中最早被搜到的点是祖先)
int d[N]; // 入度
int val[N]; // 点权
int w[N]; // 缩点后每个scc的点权和
int dp[N]; // 点权最大值
stack<int>s; // 存多个scc,每当dfn=low时就输出一个scc
vector<int>g[N]; // 原图
vector<int>G[N]; // 缩点后的新图
void dfs(int u)
{
    dfn[u]=low[u]=++tim;
    s.push(u);
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!scc[v]) // 回退边
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        cnt++;
        while(1)
        {
            int x=s.top();s.pop();
            scc[x]=cnt;
            w[cnt]+=val[x];
            if(x==u)break;
        }
    }
}
void tarjan()
{
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(scc,0,sizeof(scc));
    while(!s.empty())s.top();
    cnt=0;
    tim=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i])dfs(i);
}
void build() // 重新建图,将scc之间相连
{
    memset(d,0,sizeof(d));
    for(int i=1;i<=m;i++)
    {
        int a=scc[x[i]];
        int b=scc[y[i]];
        if(a!=b)
        {
            G[a].push_back(b); // 两个scc的祖先相连
            d[b]++; // 别忘记统计入度!
        }
    }
}
int topo() // 拓扑排序求dp值
{
    memset(dp,0,sizeof(dp));
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(low[i]!=dfn[i])continue; // 必须要是祖先节点才拓扑!
        int u=scc[i];
        if(!d[u])
        {
            dp[u]=w[u];
            q.push(u);
        }
    }
    while(!q.empty())
    {
        int u=q.front();q.pop();
        int sz=G[u].size();
        for(int i=0;i<sz;i++)
        {
            int v=G[u][i];
            d[v]--;
            dp[v]=max(dp[v],dp[u]+w[v]);
            if(!d[v])q.push(v);
        }
    }
    int mx=0;
    for(int i=1;i<=cnt;i++)
        mx=max(mx,dp[i]);
    return mx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>val[i];
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
        g[x[i]].push_back(y[i]);
    }
    tarjan();
    build();
    int sum=topo();
    printf("%d\n",sum);
    return 0;
}
/*
4 5
1 1 1 1
2 1
2 1
2 3
3 4
4 2
ans:4
*/

二、Kosaraju算法

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m,num,val[N],w[N],scc[N],d[N],dp[N];
bool vis[N];
vector<int>g[N]; // 原图
vector<int>rg[N]; // 反图
vector<int>s; // 存dfs序
vector<int>ans[N]; // 第i个scc包含的点
vector<int>G[N]; // 缩点后的新图
void dfs1(int u)
{
    if(vis[u])return;
    vis[u]=1;
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
        dfs1(g[u][i]);
    s.push_back(u);
}
void dfs2(int u)
{
    if(scc[u])return;
    scc[u]=num;
    w[num]+=val[u]; // 新的权值和(以scc为单位)
    ans[num].push_back(u); // 第num个scc包含的点
    int sz=rg[u].size(); // 注意是搜反图
    for(int i=0;i<sz;i++)
        dfs2(rg[u][i]);
}
void kosaraju()
{
    //s.clear();
    //memset(vis,0,sizeof(vis));
    //num=0;
    //memset(scc,0,sizeof(scc));
    //memset(w,0,sizeof(w));
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs1(i);
    for(int i=n-1;i>=0;i--)
    {
        int u=s[i];
        if(!scc[u])
        {
            num++;
            dfs2(u);
        }
    }
}
void build() // 重新建图,将scc之间相连
{
    //memset(d,0,sizeof(d));
    for(int i=1;i<=num;i++) // 第i个scc
    {
        int sz=ans[i].size();
        for(int j=0;j<sz;j++)
        {
            int u=ans[i][j]; // 点
            int sz1=g[u].size();
            for(int k=0;k<sz1;k++)
            {
                int v=g[u][k]; // 相邻点
                int x=scc[u];
                int y=scc[v];
                if(x!=y) 
                {
                    G[x].push_back(y);
                    d[y]++;
                }
            }
        }
    }
}
int topo() // 拓扑排序求dp值
{
    //memset(dp,0,sizeof(dp));
    queue<int>q;
    for(int i=1;i<=num;i++)
    {
        if(!d[i])
        {
            dp[i]=w[i];
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int u=q.front();q.pop();
        int sz=G[u].size();
        for(int i=0;i<sz;i++)
        {
            int v=G[u][i];
            d[v]--;
            dp[v]=max(dp[v],dp[u]+w[v]);
            if(!d[v])q.push(v);
        }
    }
    int mx=0;
    for(int i=1;i<=num;i++)
        mx=max(mx,dp[i]);
    return mx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>val[i]; // 点权
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y; // 边可以不去重
        g[x].push_back(y);
        rg[y].push_back(x);
    }
    kosaraju(); // 求scc(强连通分量)
    build(); // 建立缩点的新图
    int ans=topo();
    printf("%d\n",ans);
    return 0;
}
/*
6 6
1 1 1 1 1 1
1 2
2 3
3 4
4 2
4 6
2 5
*/