题意:约翰有n块草场，编号1到n，这些草场由m条单行道相连.贝西总是从1号草场出发，最后回到1号草场.她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次.因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行.问，贝西最多能吃到多少个草场的牧草.((n,m<=100000))
分析:首先跑tarjan缩点,缩成一个点的强连通分量记录一下size就好,通过这个点相当于通过了size个点.
然后对于缩点完之后的有向无环图,分别顺向建图跑spfa,求出dis1[i],表示以1(所在的强连通分量)为起点,i为终点的最长路,反向建图跑spfa,求出dis2[i],表示以1(所在的强连通分量)为终点,i为起点的最长路.
最后枚举一下num个强连通分量u,然后枚举u可以到达的点v,(ans=max(ans,dis1[v]+dis2[u]-size[color[1]])).
注意ans初始化为(size[color[1]]),(dis1[v])和(dis2[u])要同时大于0才能更新ans(否则78分),因为(dis1[v])和(dis2[u])都加了一次(size[color[1]]),所以要减掉一个.
因为我是先反向建图再顺向建图跑的spfa,所以当我更新答案时,我的图是顺向的,所以我枚举的(u->v)逆向过来为(v->u),所以相当于我枚举的路径是(1->v->u->1),这里别思路混乱了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=100005;
int n,m,ans,a[N],b[N];
int dis1[N],dis2[N],visit[N];
int tot,head[N],nxt[N],to[N];
int timeclock,top,num;
int dfn[N],low[N],st[N],color[N],size[N];
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u){
dfn[u]=low[u]=++timeclock;
st[++top]=u;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!color[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
color[u]=++num;
++size[num];
while(st[top]!=u){
color[st[top]]=num;
++size[num];
--top;
}
--top;
}
}
inline void spfa1(){
memset(visit,0,sizeof(visit));
queue<int> q1;q1.push(color[1]);
visit[color[1]]=1;dis1[color[1]]=size[color[1]];
while(q1.size()){
int u=q1.front();q1.pop();visit[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis1[v]<dis1[u]+size[v]){
dis1[v]=dis1[u]+size[v];
if(!visit[v]){
q1.push(v);
visit[v]=1;
}
}
}
}
}
inline void spfa2(){
memset(visit,0,sizeof(visit));
queue<int> q2;q2.push(color[1]);
visit[color[1]]=1;dis2[color[1]]=size[color[1]];
while(q2.size()){
int u=q2.front();q2.pop();visit[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis2[v]<dis2[u]+size[v]){
dis2[v]=dis2[u]+size[v];
if(!visit[v]){
q2.push(v);
visit[v]=1;
}
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;++i){
a[i]=read(),b[i]=read();
add(a[i],b[i]);
}
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
tot=0;memset(head,0,sizeof(head));
for(int i=1;i<=m;++i)
if(color[a[i]]!=color[b[i]])add(color[b[i]],color[a[i]]);
spfa2();
tot=0;memset(head,0,sizeof(head));
for(int i=1;i<=m;++i)
if(color[a[i]]!=color[b[i]])add(color[a[i]],color[b[i]]);
spfa1();
ans=size[color[1]];
for(int u=1;u<=num;++u){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis2[u]>0&&dis1[v]>0)ans=max(ans,dis2[u]+dis1[v]-size[color[1]]);
}
}
printf("%d
",ans);
return 0;
}