85pts TLE求助
查看原帖
85pts TLE求助
329672
Ninelife_Cat楼主2021/5/13 08:50

思路是 Tarjan 缩点完之后跑分层图 spfa,但它死循环了

找不出哪里写挂了k

#include<bits/stdc++.h>
#define endl '\n'
#define ri register
#define int long long
#define inf 2147483647
#define pb(x) push_back((x))
#define mp(x,y) make_pair((x),(y))
#define reset(x,y) memset((x),(y),sizeof((x)))
using namespace std;
inline int read()
{
	int x=0,f=0;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
	return f?-x:x;
}
inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
const int N=2e5+10;
int Head[N],Next[N],To[N],Cnt,head[N],next[N],to[N],cnt;
inline void Add(int x,int y) {Next[++Cnt]=Head[x];Head[x]=Cnt;To[Cnt]=y;}
//原图连边

inline void add(int x,int y) {next[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}
//分层图连边

int n,m,id,sum,x[N],y[N],dfn[N],low[N],siz[N],num[N],dis[N];
//num[x]表示x这个点在第几个强连通分量内,siz是该点的点权
stack<int> st;
bool vis[N];
inline void Tarjan(int x)
{
	dfn[x]=low[x]=++id;vis[x]=1;st.push(x);
	for(ri int i=Head[x];i;i=Next[i])
	{
		ri int y=To[i];
		if(!dfn[y]) Tarjan(y),low[x]=min(low[x],low[y]);
			else if(vis[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		ri int y;++sum;
		do y=st.top(),st.pop(),vis[y]=0,num[y]=sum,++siz[sum]; while(x!=y);
	}
}//Tarjan板子
inline void Spfa(int s)
{
	queue<int> q;reset(vis,0);q.push(s);vis[s]=1;
	while(!q.empty())
	{
		ri int x=q.front();q.pop();vis[x]=0;
		for(ri int i=head[x];i;i=next[i])
		{
			ri int y=to[i];
			if(dis[y]<dis[x]+siz[x])
			{
				dis[y]=dis[x]+siz[x];
//				if((double)clock()/CLOCKS_PER_SEC>0.95) {cout<<dis[num[1]+sum];exit(0);}
				if(!vis[y]) q.push(y),vis[y]=1;
			}
		}
	}
}//spfa求最长路
signed main()
{
	n=read();m=read();
	for(ri int i=1;i<=m;++i)
		x[i]=read(),y[i]=read(),Add(x[i],y[i]);
	for(ri int i=1;i<=n;++i)
		if(!dfn[i]) Tarjan(i);
	for(ri int i=1;i<=sum;++i)
		siz[i+sum]=siz[i];
	add(num[1],num[1]+sum);
	for(ri int i=1;i<=m;++i)
		if(num[x[i]]!=num[y[i]]) add(num[x[i]],num[y[i]]),add(num[y[i]],num[x[i]]+sum),add(num[x[i]]+sum,num[y[i]]+sum);
	Spfa(num[1]);
	cout<<dis[num[1]+sum];
	return 0;
}
2021/5/13 08:50
加载中...