洛谷P3387 【模板】缩点 题解

背景

今天\(loj\)挂了，于是就有了闲情雅致来刷\(luogu\)

题面

洛谷P3387 【模板】缩点传送门

题意

给定一个\(n\)个点\(m\)条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

思路

~~点击获得更好的阅读体验~~

\(Kosaraju\)缩点+记忆化搜索

什么是\(Kosaraju\)缩点？

与\(Tarjan\)缩点的时间复杂度差不多，都是\(O(n+m)\)。

其主要思想就是\(dfs\)两次。

核心代码如下：

void dfs_1(int x){
    vis[x]=1;
    for(int i=fir[x];i;i=nxt[i]){
        if(vis[son[i]]==0) dfs_1(son[i]);
    }
    d[++t]=x;
}
void dfs_2(int x){
    vis[x]=t;
    s[t]++;
    for(int i=fir2[x];i;i=nxt2[i]){
        if(vis[son2[i]]==0) dfs_2(son2[i]);
    }
}
void Kosaraju(){
    t=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        if(vis[i]==0) dfs_1(i);
    }

    memset(vis,0,sizeof(vis));t=0;
    for(int i=n;i>=1;i--){
        if(vis[d[i]]==0) t++,dfs_2(d[i]);
    }
}

当然，我认为\(Kosaraju\)有一定的缺点，比如说要建反边。

具体\(Kosaraju\)算法的介绍戳这里

什么是记忆化搜索

记忆化搜索（Memory search）心理学是指搜索信息的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。

——百度百科

其实说白了就是\(dp\)的进阶。多了一个搜索。。。

只不过在\(dfs\)时开了个数组存储了当前的状态，以便以后搜索需要。

关于这道题

那么这道题就愉快的解决了。。。

思路如下：

为什么有这丑陋无比的水印

CODE:（PS:请忽略边权）

#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define E 200010
using namespace std;//丑陋无比的头文件
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}//丑陋无比的读优
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}//丑陋无比的输优
int n,m,a[E];
int fir[E],nxt[E],w[E],son[E],tot;
int vis[E],d[E],top,f[E],ans;
int fir2[E],nxt2[E],w2[E],son2[E],tot2;
void add(int x,int y,int z){
    ++tot;
    nxt[tot]=fir[x];
    fir[x]=tot;
    son[tot]=y;
    w[tot]=z;
}//建正边
void add2(int x,int y,int z){
    ++tot2;
    nxt2[tot2]=fir2[x];
    fir2[x]=tot2;
    son2[tot2]=y;
    w2[tot2]=z;
}//建反边
void dfs1(int x){//Kosaraju算法第一次dfs
    vis[x]=1;
    for(int i=fir[x];i;i=nxt[i]){//正向
        int to=son[i];
        if(!vis[to]) dfs1(to);
    }
    d[++top]=x;
}
void dfs2(int x){//Kosaraju算法第二次dfs
    vis[x]=top;//标记第几个强连通分量
    for(int i=fir2[x];i;i=nxt2[i]){//反向
        int to=son2[i];
        if(!vis[to]) dfs2(to);
    }
}
void dp(int x){//记忆化搜索
    if(f[x]!=0) return ;//记忆化体现
    int ss=0;
    f[x]=d[x];
    for(int i=fir2[x];i;i=nxt2[i]){//使用新的DAG
        int to=son2[i];
        dp(to);
        ss=max(ss,f[to]);//取最大值
    }
    f[x]+=ss;//别忘记加回去
}
int main(){
    n=read();m=read();//读入
    for(int i=1;i<=n;i++) a[i]=read();//读入
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        add(x,y,1);//建正边
        add2(y,x,1);//建反边
    }
    //Kosaraju Start
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));top=0;//清空
    for(int i=1;i<=n;i++){
        if(!vis[i]) dfs1(i);//dfs第一次（正向）
    }
    memset(vis,0,sizeof(vis));top=0;//清空
    for(int i=n;i>=1;i--){
        if(!vis[d[i]]) ++top,dfs2(d[i]);//dfs第二次（反向）
    }
    //Kosaraju End
    memset(d,0,sizeof(d));//清空
    for(int i=1;i<=n;i++){
        d[vis[i]]+=a[i];//权值累计
    }
    memset(fir2,0,sizeof(fir2));tot2=0;//清空
    for(int i=1;i<=n;i++){//重新建DAG
        for(int j=fir[i];j;j=nxt[j]){
            int to=son[j];
            if(vis[i]!=vis[to]) add2(vis[i],vis[to],1);//需要两个不同的强连通分量
        }
    }
    for(int i=1;i<=top;i++){//记忆化搜索
        if(!f[i]){//记忆化
            dp(i);
            ans=max(ans,f[i]);//取最大值
        }
    }
    write(ans);putchar('\n');//输出
    return 0;//结束
}

洛谷P3387 【模板】缩点 题解

原文：https://www.cnblogs.com/yzx1798106406/p/10332596.html