[模板]（luogu P3387）縮點

前言：對於這週的咕咕咕表示好像沒什麼好表示的，完全沒有靈感a......寫東西真的好難啊......於是又玩了半天鬼泣4？？？還挺好玩的

來源：題解

题目背景

缩点+DP

题目描述

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

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

输入输出格式

输入格式：

第一行，n,m

第二行，n个整数，依次代表点权

第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

输出格式：

共一行，最大的点权之和。

输入输出样例

输入样例#1：

输出样例#1：

说明

n<=10^4,m<=10^5,点权<=1000

算法：Tarjan缩点+DAGdp

題目中給出了算法，然而第一篇題解用的是拓撲排序，所以我就照著抄了......

本來寒假學過tarjan的，然而忘記了，這次複習一開始最看不懂的是low數組：

low數組表示“從i點出發能訪問到的最早進入時間”，事實上是如果從i點出發能向上走到某個點說明這裡存在了一個環，從i發出了一條後向邊,

等dfs完這個點的分支的時候，找到的環就會是最大的了。

縮點就是每個強連通分量當做一個點，然後重新建圖

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=10000+15;
int n,m,cnt,tim,top,s;
int p[maxn],head[maxn],sd[maxn],dfn[maxn],low[maxn];
//sd為這個點在哪個強連通分量中，dfs時間戳，
//low棧中以u為父結點的子樹能連接到棧中最上端的點的dfs值
//也就是從i點出發能訪問到的最早進入時間 
//p為點權，in為入度 
int stac[maxn],vis[maxn];//栈只为了表示此时是否有父子关系
int h[maxn],in[maxn],dist[maxn]; 
struct node{
    int u,v,next;
}e[maxn*10],ed[maxn*10];
void add(int u,int v)
{
    e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void tarjan(int x)//求強連通分量，每個強連通分量就是一個新點 
{
    low[x]=dfn[x]=++tim;
    stac[++top]=x;vis[x]=1;
    
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(vis[v]){
            low[x]=min(low[x],low[v]);
        }
    }
    if(dfn[x]==low[x]){
        int y;
        while(y=stac[top--]){ 
            sd[y]=x;
            vis[y]=0;
            if(x==y)break;
            p[x]+=p[y];
        }
    }
}
//縮成了DAG圖，所以可以拓撲排序了 
//可以直接dp 
int topo()
{
    queue<int>q;
    int tot=0;
    for(int i=1;i<=n;i++)
    if(sd[i]==i&&!in[i]){//自己是這個強連通分量的根 
        q.push(i);
        dist[i]=p[i];
    }
    while(!q.empty()){
        int k=q.front();q.pop();
        for(int i=h[k];i;i=ed[i].next){
            int v=ed[i].v;
            dist[v]=max(dist[v],dist[k]+p[v]);
            in[v]--;
            if(in[v]==0)q.push(v);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    ans=max(ans,dist[i]);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&p[i]);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])tarjan(i);
    for(int i=1;i<=m;i++){//重新建圖,枚舉每一條原邊，如果不在一個強連通分量里就連上 
        int x=sd[e[i].u],y=sd[e[i].v];
        if(x!=y){
            ed[++s].next=h[x];
            ed[s].v=y;
            ed[s].u=x;
            h[x]=s;
            in[y]++;
        }
    }
    printf("%d",topo());
}