蒟蒻好紧张啊 蒟蒻好紧张啊 蒟蒻好紧张啊 蒟蒻好紧张啊
一开始方向好像走错了 乱推了个拓扑的式子 然后FST了
然后还不肯放弃 挣扎了20分钟 又受到了刚上来都打完球了的ldx的diss
"我靠，这么傻逼的题你还没A吗"
好吧的确是傻逼题
先缩点
设s是1所在的scc的编号
考虑逆行的使用姿势
对于一个可以从s出发到达的点 逆行到一个可以到达s的点
然后这个东西你可以跑正反两发spfa
最后枚举每个点 枚举出边 ans=max(ans,dis[i][1]+dis[vis][2]-num[s]);
注意是遍历反向边的数组
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 100005 using namespace std; template<class T> inline void read(T &x) { x=0; int f=1; static char ch=getchar(); while((!isdigit(ch)&&ch!='-')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); x*=f; } int n,m,tot,first[N]; struct Edge { int to,next; }edge[2*N]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } int dfn[N],low[N],sign,cnt,belong[N],num[N]; stack <int> sta; bool insta[N]; void dfs(int now) { dfn[now]=low[now]=++sign; insta[now]=true; sta.push(now); for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(!dfn[vis]) { dfs(vis); low[now]=min(low[vis],low[now]); } else if(insta[vis]) low[now]=min(dfn[vis],low[now]); } if(dfn[now]==low[now]) { int temp; cnt++; do { temp=sta.top(); num[cnt]++; belong[temp]=cnt; insta[temp]=false; sta.pop(); }while(temp!=now); } } bool inque[N]; vector <int> res1[N],res2[N]; int s,dis[N][3]; void spfa(int f,vector <int> *res) { queue <int> q; q.push(s); memset(inque,0,sizeof(inque)); dis[s][f]=num[s]; while(!q.empty()) { int now=q.front(); inque[now]=false; q.pop(); for(int i=0;i<res[now].size();i++) { int vis=res[now][i]; if(dis[now][f]+num[vis]>dis[vis][f]) { dis[vis][f]=dis[now][f]+num[vis]; if(!inque[vis]) q.push(vis),inque[vis]=true; } } } } int main() { read(n); read(m); for(int i=1,x,y;i<=m;i++) { read(x),read(y); addedge(x,y); } for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i); for(int i=1;i<=n;i++) { for(int u=first[i];u;u=edge[u].next) { int vis=edge[u].to; if(belong[i]!=belong[vis]) { res1[belong[i]].push_back(belong[vis]); res2[belong[vis]].push_back(belong[i]); } } } s=belong[1]; spfa(1,res1); spfa(2,res2); int ans=num[s]; for(int i=1;i<=cnt;i++) { if(dis[i][1]==0) continue; for(int j=0;j<res2[i].size();j++) { int vis=res2[i][j]; if(dis[vis][2]==0) continue; ans=max(ans,dis[i][1]+dis[vis][2]-num[s]); } } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9926071.html
相关资源：各显卡算力对照表！