解题：USACO15JAN Grass Cownoisseur

解题

首先缩点没啥可说的，然后考虑枚举这次逆行的边。具体来说在正常的图和反图上各跑一次最长路，然后注意减掉起点的贡献，用拓扑排序实现(我这里瞎写了个Bellman_Ford，其实在DAG上这好像和拓扑排序的复杂度是一样的=。=)

一个细节：注意可能整个图是个强连通分量，所以答案初始是起点所在的强联通分量的大小

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int dfn[N],low[N],col[N],stk[N],ins[N],inq[N],siz[N],dis[][N];

 int p[N],noww[N],goal[N],P[N][],Noww[N][],Goal[N][];

 int n,m,c,t1,t2,cnt,cnt0,cnt1,tot,top,ans;

 queue<int> qs;

 void link(int f,int t)

 {

     noww[++cnt]=p[f];

     goal[cnt]=t,p[f]=cnt;

 }

 void relink(int f,int t)

 {

     Noww[++cnt0][]=P[f][];

     Goal[cnt0][]=t,P[f][]=cnt0;

     Noww[++cnt1][]=P[t][];

     Goal[cnt1][]=f,P[t][]=cnt1;

 }

 void Tarjan_SCC(int nde)

 {

     dfn[nde]=low[nde]=++tot;

     stk[++top]=nde,ins[nde]=true;

     for(int i=p[nde];i;i=noww[i])

         if(!dfn[goal[i]])

             Tarjan_SCC(goal[i]),low[nde]=min(low[nde],low[goal[i]]);

         else if(ins[goal[i]])

             low[nde]=min(low[nde],low[goal[i]]);

     if(dfn[nde]==low[nde])

     {

         c++; int tmp;

         do

         {

             tmp=stk[top--];

             ins[tmp]=false;

             col[tmp]=c,siz[c]++;

         }while(nde!=tmp);

     }

 }

 void Bellman_Ford(int s,int t)

 {

     memset(dis[t],0xc0,sizeof dis[t]);

     dis[t][s]=siz[s],qs.push(s),inq[s]=true;

     while(!qs.empty())

     {

         int tn=qs.front();

         qs.pop(),inq[tn]=false;

         for(int i=P[tn][t];i;i=Noww[i][t])

             if(dis[t][Goal[i][t]]<dis[t][tn]+siz[Goal[i][t]])

             {

                 dis[t][Goal[i][t]]=dis[t][tn]+siz[Goal[i][t]];

                 if(!inq[Goal[i][t]])

                     qs.push(Goal[i][t]),inq[Goal[i][t]]=true;

             }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

         scanf("%d%d",&t1,&t2),link(t1,t2);

     for(int i=;i<=n;i++)

         if(!dfn[i]) Tarjan_SCC(i);

     for(int i=;i<=n;i++)

         for(int j=p[i];j;j=noww[j])

             if(col[i]!=col[goal[j]])

                 relink(col[i],col[goal[j]]);

     Bellman_Ford(col[],),Bellman_Ford(col[],),ans=siz[col[]];

     for(int i=;i<=c;i++)

         for(int j=P[i][];j;j=Noww[j][])

             ans=max(ans,dis[][i]+dis[][Goal[j][]]-siz[col[]]);

     printf("%d",ans);

     return ;

 }