前言：對於這週的咕咕咕表示好像沒什麼好表示的，完全沒有靈感a......寫東西真的好難啊......於是又玩了半天鬼泣4？？？還挺好玩的
來源：題解
题目背景
缩点+DP
题目描述
给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入输出格式
输入格式：
第一行，n,m
第二行，n个整数，依次代表点权
第三至m+2行，每行两个整数u,v，表示u->v有一条有向边
输出格式：
共一行，最大的点权之和。
输入输出样例
输入样例#1：
2 2
1 1
1 2
2 1
输出样例#1：
2
说明
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=+;
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*],ed[maxn*];
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]=; 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]=;
if(x==y)break;
p[x]+=p[y];
}
}
}
//縮成了DAG圖，所以可以拓撲排序了
//可以直接dp
int topo()
{
queue<int>q;
int tot=;
for(int i=;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]==)q.push(v);
}
}
int ans=;
for(int i=;i<=n;i++)
ans=max(ans,dist[i]);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&p[i]);
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=;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());
}