TLE了6个点,下载下来测试数据发现是死循环了,但一直没发现原因,求大佬帮助.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e4+10,M=1e5+10;
int n,m,p[N],w[N];
int head[N],head2[N],ne,ne2;
int dfn[N],low[N],idx,bel[N];
bool vis[N];
int stk[N],top,in[N],dis[N];
queue<int> qu;
struct Edge {
int v,nxt;
}e[M],e2[M];
void add_edge(int u,int v) {
e[ne].v=v;
e[ne].nxt=head[u];
head[u]=ne++;
}
void add_edge2(int u,int v) {
e2[ne].v=v;
e2[ne].nxt=head2[u];
head2[u]=ne2++;
}
void tarjan(int x) {
dfn[x]=low[x]=++idx;
stk[++top]=x;
vis[x]=true;
for(int i=head[x];~i;i=e[i].nxt) {
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],dfn[v]);
}
}
if(low[x]==dfn[x]) {
while(stk[top+1]!=x) {
bel[stk[top]]=x;
vis[stk[top]]=false;
w[x]+=p[stk[top]];
top--;
}
}
}
void topo() {
for(int i=1;i<=n;i++) {
if(bel[i]==i&&!in[i]) {
qu.push(i);
dis[i]=w[i];
}
}
while(!qu.empty()) {
int k=qu.front();
qu.pop();
for(int i=head2[k];~i;i=e2[i].nxt) {
int v=e2[i].v;
in[v]--;
dis[v]=max(dis[v],dis[k]+w[v]);
if(!in[v]) {
qu.push(v);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(head,-1,sizeof(head));
memset(head2,-1,sizeof(head2));
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=m;i++) {
int u,v;
cin>>u>>v;
add_edge(u,v);
}
for(int i=1;i<=n;i++) {
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=n;i++) {
for(int j=head[i];~j;j=e[j].nxt) {
int v=e[j].v;
if(bel[i]!=bel[v]) {
add_edge2(bel[i],bel[v]);
in[bel[v]]++;
}
}
}
topo();
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
cout<<ans;
return 0;
}