来自蒟蒻的题解

*orz-orz写了超级久啊*

表示写之前都不会spfa啊（求大佬勿喷QAQ)

1. 缩点，变成DAG。

2. 求每个点到1所在scc的路径权值和f1，1所在的scc到每个点的路径权值和f2。

3. 枚举一条边（u->v），用f1[v]+f2[u]+1所在bsz中更新答案。

其实就是一个Tarjan模板+spfa模板+重构图

好像不难

首先需要穿*库头*

        #include <iostream>
        #include <cstring>
        #include <cstdio>
        #include <stack>
        #include <queue>
        #include<cmath>
        using namespace std;
        const int maxn=1e5+50;

然后定义一些数组啊

            int n,m,S;
            int tot,idx,dfn[maxn],low[maxn];
            stack<int> st;
            bool ins[maxn];
            int belong[maxn],bsz[maxn];
            int f1[maxn],f2[maxn];
            bool vis[maxn];

我用的是链式前向星存图啊 然后至于权值 自己思考一下

        struct nd{
                    int fr,to,ne,op;
                }e[maxn],t[maxn];
                int he[maxn], cnt;
                void add(int a,int b,int w=1){ 
                    cnt++;
                    e[cnt].fr=a;
                    e[cnt].to=b; 
                    e[cnt].ne=he[a];
                    he[a]=cnt;
                    e[cnt].op=w;
                }

然后Tarjan的模板 ~~没什么好解释的 ~~大家应该都会

       void tarjan(int u){
            dfn[u]=low[u]=++idx;
            st.push(u);
            ins[u]=true;
            for(int i=he[u];i;i=e[i].ne){
                int v=e[i].to;
                if(!dfn[v]){
                    tarjan(v);
                    low[u]=min(low[u],low[v]);
                }
                else if(ins[v])low[u]=min(low[u],dfn[v]);        
            }
            if(low[u]==dfn[u]){
                tot++;
                int x=0;
                while(x!=u){
                    x=st.top();
                    st.pop();
                    ins[x]=false;
                    belong[x]=tot;
                    bsz[tot]++;
                }
            }
        }

然后重构图( ⊙ o ⊙ )

        void rebuild(){
            for(int i=1;i<=cnt;i++) t[i]=e[i];
            int total=cnt;
            cnt=0;
            memset(he,0,sizeof(he));
            for(int i=1;i<=total;i++){
                int u=t[i].fr, v=t[i].to;
                u=belong[u];
                v=belong[v];
                if(u!=v){
                    add(u,v,1);
                    add(v,u,0);
                }
            }
        }

最后~(≧▽≦)/~spfa 当然几乎没改 纯模板

         void spfa(int p,int d[]){
                memset(vis,false,sizeof(vis));
                queue<int> q;
                q.push(S);
                d[S]=0;
                while(!q.empty()){
                    int u=q.front();
                    q.pop();
                    vis[u]=false;
                    for(int i=he[u];i;i=e[i].ne){
                        if(e[i].op!=p) continue;
                        int v=e[i].to;
                        if(d[v]<d[u]+bsz[v]){
                                d[v]=d[u]+bsz[v]; 
                                if(!vis[v]){
                                vis[v]=true;
                                q.push(v);
                            }
                        }
                    }
                }
            }

部分主函数部分

        S=belong[1];
            rebuild();
            n=tot;
            for(int i=1;i<=n;i++)f1[i]=f2[i]=-maxn;
            spfa(1,f1);spfa(0,f2);
            int ans=bsz[S];
            for(int i=1;i<=cnt;i++){
                int u=e[i].fr,v=e[i].to;
                ans=max(ans,f1[v]+f2[u]+bsz[S]);
            }

请勿copy

建议自己思考主要过程 最好画图模拟一下

祝各位神犇刷题愉快！！

orz望神佬勿喷qwq