标记数组退栈时未改变
by kaxaw @ 2022-11-25 14:25:44
@[kaxaw](/user/579060) 现在50pts啦 :)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+1;
const int maxm=1e5+1;
const int inf=0x3f3f3f3f;
struct edge{
int from,to,next;
}e0[maxm],e1[maxm];
int n,m,ans,tot0,tot1,cnt,h0[maxn],h1[maxn],in[maxn],d[maxn],siz[maxn];
int a[maxn],tim,dfn[maxn],low[maxn],vis[maxn],state[maxn];
stack <int> st;
queue <int> q;
inline void addEdge0(int x,int y){
e0[++tot0]=(edge){x,y,h0[x]};
h0[x]=tot0;
}
inline void addEdge1(int x,int y){
e1[++tot1]=(edge){x,y,h1[x]};
h1[x]=tot1;
in[y]++;
}
inline void dfs(int x){
dfn[x]=low[x]=++tim;
st.push(x);
vis[x]=1;
for (int i=h0[x];i;i=e0[i].next){
int v=e0[i].to;
if (!vis[v]){
dfs(v);
low[x]=min(low[x],low[v]);
}else if (vis[v]==1) low[x]=min(low[x],dfn[v]);
}
if (low[x]==dfn[x]){
cnt++;
while (!st.empty()){
state[st.top()]=cnt;
siz[cnt]+=a[st.top()];
vis[st.top()]=2;
st.pop();
}
}
}
inline void topo(){
for (int i=1;i<=cnt;i++){
if (!in[i]){
d[i]=siz[i];
q.push(i);
}
}
while (!q.empty()){
int now=q.front();
q.pop();
for (int i=h1[now];i;i=e1[i].next){
int v=e1[i].to;
d[v]=max(d[v],d[now]+siz[v]);
if (!--in[v]) q.push(v);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
addEdge0(u,v);
}
for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
for (int i=1;i<=tot0;i++){
int u=e0[i].from,v=e0[i].to;
if (state[u]!=state[v]) addEdge1(state[u],state[v]);
}
topo();
for (int i=1;i<=cnt;i++) ans=max(ans,d[i]);
printf("%d\n",ans);
return 0;
}
```
by TimSwn090306 @ 2022-11-25 14:35:40
退栈的时候不是把栈清空，清到栈顶为 x 时就要退出了
by TangBin0524 @ 2022-11-25 14:45:49
@[TangBin0524](/user/412188) 是这样吗？（我太笨了
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+1;
const int maxm=1e5+1;
const int inf=0x3f3f3f3f;
struct edge{
int from,to,next;
}e0[maxm],e1[maxm];
int n,m,ans,tot0,tot1,cnt,h0[maxn],h1[maxn],in[maxn],d[maxn],siz[maxn];
int a[maxn],tim,dfn[maxn],low[maxn],vis[maxn],state[maxn];
stack <int> st;
queue <int> q;
inline void addEdge0(int x,int y){
e0[++tot0]=(edge){x,y,h0[x]};
h0[x]=tot0;
}
inline void addEdge1(int x,int y){
e1[++tot1]=(edge){x,y,h1[x]};
h1[x]=tot1;
in[y]++;
}
inline void dfs(int x){
dfn[x]=low[x]=++tim;
st.push(x);
vis[x]=1;
for (int i=h0[x];i;i=e0[i].next){
int v=e0[i].to;
if (!vis[v]){
dfs(v);
low[x]=min(low[x],low[v]);
}else if (vis[v]==1) low[x]=min(low[x],dfn[v]);
}
if (low[x]==dfn[x]){
cnt++;
while (!st.empty()){
if (st.top()==x) break;
state[st.top()]=cnt;
siz[cnt]+=a[st.top()];
vis[st.top()]=2;
st.pop();
}
}
}
inline void topo(){
for (int i=1;i<=cnt;i++){
if (!in[i]){
d[i]=siz[i];
q.push(i);
}
}
while (!q.empty()){
int now=q.front();
q.pop();
for (int i=h1[now];i;i=e1[i].next){
int v=e1[i].to;
d[v]=max(d[v],d[now]+siz[v]);
if (!--in[v]) q.push(v);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
addEdge0(u,v);
}
for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
for (int i=1;i<=tot0;i++){
int u=e0[i].from,v=e0[i].to;
if (state[u]!=state[v]) addEdge1(state[u],state[v]);
}
topo();
for (int i=1;i<=cnt;i++) ans=max(ans,d[i]);
printf("%d\n",ans);
return 0;
}
```
by TimSwn090306 @ 2022-11-25 15:04:14
不是的，这样写如果这个强连通分量大小为 1 的话就直接 break 了，应该要用do_while语句。我写这个题的时候手写栈，就很方便。
```cpp
do{
state[st.top()]=cnt;
siz[cnt]+=a[st.top()];
vis[st.top()]=2;
}while(st[top--]!=x);
```
但你这个用 STL 的话，我只想出一个不太好的方法，先 push 进去一个，然后 pop 抵消掉，每轮先判断 top() 是不是 x,然后在开头 pop(),最后还要 pop() 一次。
把你的 while 循环改为这个就可以 AC。
```cpp
st.push(100000);
do{
st.pop();
state[st.top()]=cnt;
siz[cnt]+=a[st.top()];
vis[st.top()]=2;
}while(st.top()!=x);
st.pop();
```
by TangBin0524 @ 2022-11-25 15:15:06
@[TangBin0524](/user/412188) OKOK我AC了，用的这个↓ ~~（照搬一遍~~
```cpp
if (low[x]==dfn[x]){
cnt++;
while (!st.empty()){
if (st.top()==x) break;
state[st.top()]=cnt;
siz[cnt]+=a[st.top()];
vis[st.top()]=2;
st.pop();
}
state[st.top()]=cnt;
siz[cnt]+=a[st.top()];
vis[st.top()]=2;
st.pop();
}
```
诚挚地谢谢您【玫瑰】
by TimSwn090306 @ 2022-11-25 15:20:51
时隔半年回来批判一下我奇怪的脑回路（（
其实记录一下st.top()，执行完后判断是否==x 就行了 ~~（wssb~~
```cpp
if (low[x]==dfn[x]){
cnt++;
while (!st.empty()){
int now=st.top();
st.pop();
state[now]=cnt;
siz[cnt]+=a[now];
vis[now]=2;
if (now==x) break;
}
}
```
by TimSwn090306 @ 2023-06-07 22:52:59