题解 P3387 【【模板】缩点】
大佬们好，我这个蒟蒻又来发题解了。（这是今年发的第一篇题解）
其实这题标题已经很清楚了，缩点！！！！！ 但这不仅仅是缩点。
这还要DP！！！蒟蒻一开始打的暴力
可以发现每个强连通块都可以缩成一个点，这些点可以拓扑一下。
然后按层数DP就行了！！蒟蒻调了一个小时.......
具体注意事项见程序
#include<bits/stdc++.h>
#include<cctype>
#include<vector>
#include<map>
using namespace std;
inline int read(){//快读
int x=0,w=1;
char c;
c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
w=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*w;
}
vector<int>a[100005],sta[100005],daa[100005],bb,cengshu[100005];
map<long long,bool>hh;
int ff[1000005],rudu[1000050],ll,dab[1000005],b[1000005],t,tt[1000005],h[1000005],ans,n,nn,m,i,j,k,l,s,d,f,top,r,c[1000005],ins[1000005],tmp,dfn[1000005],low[1000005],num;
void tarjan(int x){//就是tarjan求强连通块
dfn[x]=low[x]=++num;
ins[x]=1;
c[++top]=x;
for(int i=0;i<a[x].size();i++){
int y=a[x][i];
if(dfn[y]==0){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else
if(ins[y]==1){
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
int y;
t++;
do{
y=c[top];
top--;
ins[y]=0;
sta[t].push_back(y);
h[y]=t;
}while(x!=y);
}
return;
}
void topu(){//一个拓扑分层
memset(rudu,0,sizeof(rudu));
for(int i=1;i<=nn;i++){
for(int j=0;j<daa[i].size();j++){
rudu[daa[i][j]]++;
}
}
for(int i=1;i<=nn;i++){
if(rudu[i]==0){
bb.push_back(i);
}
}
int ss=0,cmm=0;;
while(ss<nn){
if(bb.empty()){
return;
}
cmm++;
for(int i=0;i<bb.size();i++){
cengshu[cmm].push_back(bb[i]);
}
l=bb.size();
ss+=l;
for(int i=0;i<bb.size();i++){
tt[i+1]=bb[i];
}
bb.clear();
for(int i=1;i<=l;i++){
for(int j=0;j<daa[tt[i]].size();j++){
rudu[daa[tt[i]][j]]--;
if(rudu[daa[tt[i]][j]]==0){
bb.push_back(daa[tt[i]][j]);
}
}
}
}
ll=cmm;
return;
}
int main(){
freopen("h.in","r",stdin);
freopen("h.out","w",stdout);
n=read();m=read();
for(i=1;i<=n;i++){
b[i]=read();
}
for(i=1;i<=m;i++){
f=read();
r=read();
a[f].push_back(r);
}
memset(c,0,sizeof(c));
memset(ins,0,sizeof(ins));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(h,0,sizeof(h));
num=0;
top=0;
t=0;
for(i=1;i<=n;i++){
if(dfn[i]==0){
tarjan(i);
}
}
nn=t;
for(i=1;i<=nn;i++){
dab[i]=0;
for(j=0;j<sta[i].size();j++){
dab[i]+=b[sta[i][j]];
}
}
hh.clear();
int mad=10000000;
for(i=1;i<=n;i++){
for(j=0;j<a[i].size();j++){
if(hh[h[i]*mad+h[a[i][j]]]==false&&h[i]!=h[a[i][j]]){
hh[h[i]*mad+h[a[i][j]]]=true;
daa[h[i]].push_back(h[a[i][j]]);
}
}
}
ans=0;
/*cout<<nn<<endl;
for(i=1;i<=nn;i++){
cout<<i<<" ";
for(j=0;j<sta[i].size();j++){
cout<<sta[i][j]<<" ";
}
cout<<endl;
}
for(i=1;i<=nn;i++){
for(j=0;j<daa[i].size();j++){
cout<<i<<","<<daa[i][j]<<endl;
}
}*/
topu();
memset(ff,0,sizeof(ff));
for(i=0;i<cengshu[1].size();i++){
ff[cengshu[1][i]]=dab[cengshu[1][i]];
}
for(i=2;i<=ll;i++){
for(j=0;j<cengshu[i].size();j++){
for(k=0;k<cengshu[i-1].size();k++){
if(hh[cengshu[i-1][k]*mad+cengshu[i][j]]==true){
ff[cengshu[i][j]]=max(ff[cengshu[i][j]],ff[cengshu[i-1][k]]+dab[cengshu[i][j]]);
}
}
}
}
for(i=1;i<=nn;i++){
ans=max(ans,ff[i]);
}
cout<<ans<<endl;
return 0;
}