一、缩点
题目链接
https://www.luogu.com.cn/problem/P3387
题目大意
题目思路
缩点 + 拓扑序 + dp
代码
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<set>
#define pi pair<int,int>
const int N = 1e4 + 5,M = 1e5 + 5;
using namespace std;
int n,m;
int h[N],ne[M],e[M],idx;
int h1[N],ne1[M],e1[M],idx1;
int stk[N],in_stk[N],top;
int dfn[N],low[N],fa[N],timestamp;
int a[N];
int din[N];
pi edge[M];
int dp[N];
set<pi>s;
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void add1(int a,int b){
e1[idx1] = b;
ne1[idx1] = h1[a];
h1[a] = idx1++;
}
void tarjan(int x){
dfn[x] = low[x] = ++ timestamp;
stk[++top] = x;in_stk[x] = 1;
for(int i = h[x];~i;i = ne[i]){
int y = e[i];
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x],low[y]);
}else if(in_stk[y]){
low[x] = min(low[x],dfn[y]);
}
}
if(dfn[x] == low[x]){
int y;
do{
y = stk[top--];in_stk[y] = 0;
fa[y] = x;
if(x == y) break;
a[x] += a[y];
}while(true);
}
}
int topsort(){
queue<int>q;
int ans = 0;
for(int i = 1;i <= n;++i){
if(fa[i] == i && din[i] == 0){
q.push(i);
dp[i] = a[i];
ans = max(ans,dp[i]);
}
}
while(!q.empty()){
int u = q.front();q.pop();
for(int i = h1[u];~i;i = ne1[i]){
int v = e1[i];
dp[v] = max(dp[v],dp[u] + a[v]);
ans = max(ans,dp[v]);
--din[v];
if(din[v] == 0) q.push(v);
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof(h));
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
for(int i = 1;i <= m;++i){
int x,y;scanf("%d%d",&x,&y);add(x,y);
edge[i] = {x,y};
}
for(int i = 1;i <= n;++i){
if(!dfn[i]) tarjan(i);
}
memset(h1,-1,sizeof(h1));
for(int i = 1;i <= m;++i){
int x = fa[edge[i].first],y = fa[edge[i].second];
if(x != y && !s.count({x,y})){
add1(x,y);
++din[y];
s.insert({x,y});
}
}
printf("%d",topsort());
return 0;
}
标签:tarjan,int,stk,dfn,low,include
From: https://www.cnblogs.com/gebeng/p/18137438