P3387 【模板】缩点 题解
yzxoi
·
·
题解
背景
今天loj挂了，于是就有了闲情雅致来刷luogu
题面
洛谷P3387 【模板】缩点传送门
题意
给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
思路
~~点击获得更好的阅读体验~~
### 什么是$Kosaraju$缩点？
与$Tarjan$缩点的**时间复杂度**差不多，都是$O(n+m)$。
其主要思想就是$dfs$两次。
核心代码如下：
```C++
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$算法的介绍[戳这里](https://yuzhengxi.blog.luogu.org/su-dian-qiu-qiang-lian-tong-fen-liang-kosaraju-suan-fa)
### 什么是记忆化搜索
> 记忆化搜索（Memory search）心理学是指搜索信息的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。
>
> ——百度百科
其实说白了就是$dp$的进阶。多了一个搜索。。。
只不过在$dfs$时开了个数组存储了当前的状态，以便以后搜索需要。
### 关于这道题
那么这道题就愉快的解决了。。。
思路如下：
~~为什么有这丑陋无比的水印~~
CODE:（PS:请忽略边权）
```C++
#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;//结束
}
```