题解 P3387 【【模板】缩点】

George1123 · 2019-10-22 11:55:48 · 题解

{\color{orange}\text{欢迎拜访我这个蒟蒻的博客}}

P3387 【【模板】缩点】

此题算法:tarjan缩点+拓扑排序

大致思路:

1. 输入点权pntw[]，建初始图ori。

2.tarjan缩点。建缩点后新图tag。

3. 拓扑排序，其中dp[]为最长路数组，sum[]为每个强连通分量中的点权和，满足:

以下是代码+注释

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int M=1e5+10;
int n,m,pntw[N],ans;
struct edge{
    int adj,nex;
};
struct graph{
    edge e[M*2];
    int g[N],top;
    void add(int x,int y){
        e[++top]=(edge){
            y,g[x]
        }; g[x]=top;
    }
}ori,dag; //原图和缩点图
int dfn[N],low[N],
ind,col[N],cnt,sum[N];
stack<int> s;
bool in[N];
void tarjan(int x){ //tarjan缩点
    dfn[x]=low[x]=++ind;
    s.push(x); in[x]=1;
    for(int i=ori.g[x];i;i=ori.e[i].nex){
        int to=ori.e[i].adj;
        if(!dfn[to]){
            tarjan(to);
            low[x]=min(low[x],low[to]);
        } else if(in[to])
            low[x]=min(low[x],dfn[to]);
    } if(low[x]==dfn[x]){
        int tmp=0; cnt++;
        while(tmp!=x){
            tmp=s.top(); s.pop();
            col[tmp]=cnt;
            sum[cnt]+=pntw[tmp];
            in[tmp]=0;
        }
    }
} int rud[N],dp[N]; //rud[]为每个强连通分量的入度数组
queue<int> q;
void toposort(){ //拓扑排序并求最长路
    for(int i=1;i<=cnt;i++)
        if(rud[i]==0){
            q.push(i);
            dp[i]=sum[i];
        }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=dag.g[now];i;i=dag.e[i].nex){
            int to=dag.e[i].adj; rud[to]--;
            dp[to]=max(dp[to],dp[now]+sum[to]);
            if(!rud[to]) q.push(to);
        }
    } for(int i=1;i<=n;i++)
        ans=max(ans,dp[i]);
} int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",pntw+i);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        ori.add(a,b);
    } for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=ori.g[i];j;j=ori.e[j].nex){
            int to=ori.e[j].adj;
            if(col[i]!=col[to]){ //建缩图
                dag.add(col[i],col[to]);
                rud[col[to]]++;
            }
        }
    toposort();
    printf("%d\n",ans);
    return 0;
}

我还是太蒻了，

谢谢大家! !