求助缩点模板,好像是里面死循环了
查看原帖
求助缩点模板,好像是里面死循环了
141577
yhc12345楼主2021/7/13 10:43

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;
}

2021/7/13 10:43
加载中...