如果考虑没有逆行操作的时候，我们想到缩点，然后在DAG图上随便就能搞出来，加入逆行操作后：（在DAG图上）
1.逆行操作相当于把DAG图的一条边变成无向边走两次，所以可以考虑分层图
先复制一层图，编号n+1~n+n，对于每个原图中的点向所有指向它的边建一条反边指向另外一层，表示我可以从这个点逆行到下一层，而下一层全部是逆行后的状态，无法回到上一层，这样把点的size当做边权跑最长路就正确了
2.乱搞
分别预处理出以1号点为起点和终点的最长路dis1，dis2，逆行所产生的效果是这样的：
这样答案显然对于边x->y，答案为$dis1[y]+dis2[x]pmsize[1]$（根据计算dis时包不包含1号点size决定），且dis1[y]、dis2[x]不为0（即可达）
题解里还有拆1号点拓扑排序的做法也很好
代码：
1.我不知道为什么但我的spfa真的T了.....WDMND（GKNMLGB
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn=100009; inline int read(){ register int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return (f==1)?x:-x; } int n,m,tot; struct node{ int v,nxt; }e[maxn],ed[maxn]; int head[maxn],cnt,head2[maxn],cnt2; inline void add(int u,int v){ e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt; } inline void add2(int u,int v){ ed[++cnt2].v=v;ed[cnt2].nxt=head2[u];head2[u]=cnt2; } int tim,top,s; int vis[maxn],stac[maxn],id[maxn],siz[maxn<<1],low[maxn],dfn[maxn]; bool v[maxn<<1]; void tarjan(int x){ low[x]=dfn[x]=++tim; stac[++top]=x;vis[x]=1; for(int i=head[x];i;i=e[i].nxt){ int y=e[i].v; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); } else if(vis[y]) low[x]=min(low[x],low[y]); } // if(dfn[x]==low[x]){ // int y;tot++; // while(y=stac[top--]){ // id[y]=x; // vis[y]=0; // if(x==y)break; // siz[x]+=siz[y]; // } // } if(dfn[x]==low[x]){ tot++; while(stac[top]!=x){ id[stac[top]]=tot; vis[stac[top]]=0; siz[tot]++; top--; } id[stac[top]]=tot; vis[stac[top]]=0; siz[tot]++; top--; } } queue<int>q; int dis[maxn<<1]; void spfa(){ q.push(id[1]);v[id[1]]=1; while(!q.empty()){ int x=q.front();q.pop();v[x]=0; for(int i=head2[x];i;i=ed[i].nxt){ int y=ed[i].v; if(dis[y]<dis[x]+siz[x]){ dis[y]=dis[x]+siz[x]; if(!v[y])q.push(y),v[y]=1; } } } } int main(){ freopen("testdata (2).in","r",stdin); n=read(),m=read(); // for(int i=1;i<=n;i++)siz[i]=1; for(int i=1,u,v;i<=m;i++){ u=read(),v=read(); add(u,v); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=tot;i++)siz[i+tot]=siz[i]; for(int x=1;x<=n;x++) for(int i=head[x];i;i=e[i].nxt){ int y=e[i].v; if(id[x]==id[y])continue; add2(id[x],id[y]); add2(id[y],id[x]+tot);//加两层之间的边 add2(id[x]+tot,id[y]+tot);//加第二层的边 } spfa(); printf("%d ",dis[id[1]+tot]); }