题目描述
约翰有n块草场，编号1到n，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。
贝西总是从1号草场出发，最后回到1号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。问，贝西最多能吃到多少个草场的牧草。
输入输出格式
输入格式：
第一行：草场数n，道路数m。
以下m行，每行x和y表明有x到y的单向边，不会有重复的道路出现。
输出格式：
一个数，逆行一次最多可以走几个草场。
代码
写拓扑排序写挂了，临时改了一个spfa，有点丑๑乛◡乛๑。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=100000+5; inline void read(int &x){ x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} } int n,m,tot,idx,top,cnt,ans,tot2; int head[maxn],head2[maxn],u[maxn],v[maxn],w[maxn],dis1[maxn],dis2[maxn]; int dfn[maxn],low[maxn],B[maxn],sta[maxn],du[maxn]; bool instack[maxn],inq[maxn]; queue<int> q; struct node{ int from,next,to; }e[maxn],e2[maxn]; inline void ins(int from,int to){ e[++tot].next=head[from]; e[tot].to=to; e[tot].from=from; head[from]=tot; } inline void ins2(int from,int to){ e2[++tot2].next=head2[from]; e2[tot].to=to; head2[from]=tot; } void tarjan(int x){ dfn[x]=low[x]=++idx; sta[++top]=x; instack[x]=true; for(int i=head[x];i;i=e[i].next) if(!dfn[e[i].to]){ tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); }else if(instack[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); if(dfn[x]==low[x]){ int y; ++cnt; do{ y=sta[top--]; instack[y]=false; B[y]=cnt; ++w[cnt]; }while(x!=y); } } void spfa1(int x){ memset(dis1,-0x3f,sizeof(dis1)); q.push(x); inq[x]=true; dis1[x]=w[x]; while(!q.empty()){ int u=q.front(); q.pop(); inq[u]=false; for(int i=head[u];i;i=e[i].next){ int to=e[i].to; if(dis1[to]<dis1[u]+w[to]){ dis1[to]=dis1[u]+w[to]; if(!inq[to]){ q.push(to); inq[to]=true; } } } } } void spfa(int x){ memset(dis2,-0x3f,sizeof(dis2)); q.push(x); inq[x]=true; dis2[x]=0; while(!q.empty()){ int u=q.front(); q.pop(); inq[u]=false; for(int i=head2[u];i;i=e2[i].next){ int to=e2[i].to; if(dis2[to]<dis2[u]+w[to]){ dis2[to]=dis2[u]+w[to]; if(!inq[to]){ q.push(to); inq[to]=true; } } } } } int main(){ read(n);read(m); for(int i=1;i<=m;++i){ read(u[i]);read(v[i]); ins(u[i],v[i]); } for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); memset(head,0,sizeof(head)); tot=0; for(int i=1;i<=m;++i) if(B[u[i]]!=B[v[i]]) ins(B[u[i]],B[v[i]]),ins2(B[v[i]],B[u[i]]); spfa1(B[1]);spfa(B[1]); for(int i=1;i<=tot;++i) ans=max(ans,dis2[e[i].from]+dis1[e[i].to]); printf("%d ",ans); return 0; }