[USACO15JAN]草鉴定

Link
一道及其智障的题目，关键在于博主调这个智障题调了基本一天…
其实不是很难想，我们先缩一下点，把新图建出来，当然是因为要保证图无环，要不然下面就没法做了。
这里实际上要建两个新图，一个正着的，还有一个反图。
干什么用的呢？主要就是因为题目要求回到原点，这个玩意怎么实现的问题。
首先这个路经肯定是一个圈，然后我们就可以找一下这个圈的一个“转折节点”，实际上就是枚举一个中间节点$X$，然后吧路经分为$1 -> X$和$X -> 1$两个链，这就需要我们建一个反图来进行实现。
因为题目要求经过的点最多，因此我们就跑两个最长路。
第一个最长路记录正图的$1 - > Point_i$节点为$D[i]$。
第二个最长路记录反图的$Point_i - > 1$节点为$D2[i]$。（实际上也是从1节点出发）
然后对于这个逆行的边我们如下处理：
首先在$Tarjan$的时候进行一个记录$C[i]$表示$SCCi$号节点里面包含的原图的点数。
那么$C[B[i]]$就是表示原图$i$号节点所属的$SCC$节点包含的原图的点数。
对于逆行的边我们直接枚举
答案就是$min(Ans, D[V[j].F] + D2[V[j].T] + C[B[1]])$（V为反图）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std ;

typedef long long LL ;
const int MAXN = 1010000 ;
const int MAXM = 200010 ;
const int Inf = 0x7fffffff ;

int N, M, B[MAXN], Low[MAXN], Dfn[MAXN << 1] ;
struct EDGE { int F, T, Next ;} E[MAXM << 1] ;
struct GDGE { int F, T, Next ;} G[MAXM << 1] ;
struct VDGE { int F, T, Next ;} V[MAXM << 1] ;
int Ken, Top, S[MAXN], Cnt, C[MAXN],Ans ;
bool Insta[MAXN] ;
vector <int> Point[MAXN] ;

inline int Read() {
    int X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

int H[MAXN], Tot ;
inline void Add(int F, int T) {
    E[++ Tot].F = F ; E[Tot].T = T ;
    E[Tot].Next = H[F], H[F] = Tot ;
}
int H2[MAXN], Tot2 ;
inline void Add2(int F, int T) {
    G[++ Tot2].F = F ; G[Tot2].T = T ;
    G[Tot2].Next = H2[F], H2[F] = Tot2 ;
}
int H3[MAXN], Tot3 ;
inline void Add3(int F, int T) {
    V[++ Tot3].F = F ; V[Tot3].T = T ;
    V[Tot3].Next = H3[F], H3[F] = Tot3 ;
}

inline void Tarjan(int Now) {
    Dfn[Now] = ++ Ken ; Low[Now] = Ken ;
    S[++ Top] = Now ; Insta[Now] = 1 ;
    for (int i = H[Now] ;  i ; i = E[i].Next)
        if (! Dfn[E[i].T]) {
            Tarjan(E[i].T) ;
            Low[Now] = min(Low[Now], Low[E[i].T]) ;
        }   else if (Insta[E[i].T])
            Low[Now] = min(Low[Now], Dfn[E[i].T]) ;
    if (Dfn[Now] == Low[Now]) {
        int Pass ; Cnt ++ ;
        do {
            Pass = S[Top --] ;
            B[Pass] = Cnt ;
            Point[Cnt].push_back(Pass) ;
            C[Cnt] ++ ;
            Insta[Pass] = false ;
        }   while (Pass != Now) ;
    }
}

int D[MAXN], Vis[MAXN] ;
queue<int> Q ;
inline void Spfa() {
    memset(Vis, 0, sizeof(Vis)) ;
    memset(D, 0, sizeof(D)) ;
    D[B[1]] = - C[B[1]] ; Vis[B[1]] = 1 ; Q.push(B[1]) ;
    while (! Q.empty()) {
        int Now = Q.front() ; Q.pop() ; Vis[Now] = false ;
        for (int i = H2[Now] ; i ; i = G[i].Next)
            if (D[G[i].T] > D[Now] - C[G[i].T]) {
                D[G[i].T] = D[Now] - C[G[i].T] ;
                if (! Vis[G[i].T])
                    Vis[G[i].T] = 1, Q.push(G[i].T) ;
            }
    }
}

int D2[MAXN] ;
inline void Spfa2() {
    memset(D2, 0, sizeof(D2)) ;
    memset(Vis, 0, sizeof(Vis)) ;
    while (! Q.empty()) Q.pop() ;
    D2[B[1]] = - C[B[1]] ; Vis[B[1]] = 1 ; Q.push(B[1]) ;
    while (! Q.empty()) {
        int Now = Q.front() ; Q.pop() ; Vis[Now] = false ;
        for (int i = H3[Now] ; i ; i = V[i].Next)
            if (D2[V[i].T] > D2[Now] - C[V[i].T]) {
                D2[V[i].T] = D2[Now] - C[V[i].T] ;
                if (! Vis[V[i].T])
                    Vis[V[i].T] = 1, Q.push(V[i].T) ;
            }
    } 
}

int main() {
    N = Read() ; M = Read() ;
    for (int i = 1 ; i <= M ; i ++) {
        int A = Read(), B = Read() ;
        Add(A, B) ;
    }
    
    for (int i = 1 ; i <= N ; i ++)
        if (! Dfn[i]) Tarjan(i) ;

    for (int i = 1 ; i <= Cnt ; i ++)
    for (int j = 0 ; j < Point[i].size() ; j ++)
        for (int k = H[Point[i][j]] ; k ; k = E[k].Next)
            if (B[Point[i][j]] != B[E[k].T]) {
                Add2(B[Point[i][j]], B[E[k].T]) ;
                Add3(B[E[k].T], B[Point[i][j]]) ;
            }

    Spfa() ; Spfa2() ;
    for (int i = 1 ; i <= Cnt ; i ++)
    for (int j = H3[i] ; j ; j = V[j].Next) {
        if (D[V[j].F] < 0 && D2[V[j].T] < 0)
            Ans = min(Ans, D[V[j].F] + D2[V[j].T] + C[B[1]]) ;
    }
    printf("%d", - Ans) ;
    return 0 ;
}