LG3119 「USACO2015JAN」Grass Cownoisseur

问题描述

LG3119

题解

显然，如果有个环，一定是全部走完的。

所以缩点，缩出一个 \(\mathrm{DAG}\) 。

只能走一次反向，于是在正图和反图上各跑一次，枚举边，取 \(\mathrm{max}\) 即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define maxn 100007

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') {
        ch=getchar();fh=-1;
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

int n,dfn[maxn],low[maxn];
int m,Head1[maxn],Next1[maxn],to1[maxn],u1[maxn],tot1;
int Head2[maxn],Next2[maxn],to2[maxn],u2[maxn],tot2;
int Head3[maxn],Next3[maxn],to3[maxn],u3[maxn],tot3;
int xx,yy;
int stac[maxn],top,ind,cnt;

int sd[maxn],val[maxn];
bitset<maxn>ins;
void tarjan(int x){
    dfn[x]=low[x]=++ind;stac[++top]=x;
    ins[x]=1;
    for(int i=Head1[x];i;i=Next1[i]){
        int y=to1[i];
        if(dfn[y]) {if(ins[y]) low[x]=min(low[x],dfn[y]);}
        else{
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
    }
    if(dfn[x]==low[x]){
        cnt++;val[cnt]=1;
        while(stac[top]!=x){
            ins[stac[top]]=0;sd[stac[top]]=cnt;top--;++val[cnt];
        }
        sd[stac[top]]=cnt;top--;ins[x]=0;
    }
}

void add1(int x,int y){
    to1[++tot1]=y,Next1[tot1]=Head1[x],Head1[x]=tot1,u1[tot1]=x;
}

void add2(int x,int y){
    to2[++tot2]=y,Next2[tot2]=Head2[x],Head2[x]=tot2,u2[tot2]=x;
}

void add3(int x,int y){
    to3[++tot3]=y,Next3[tot3]=Head3[x],Head3[x]=tot3,u3[tot3]=x;
}

set <pair<int,int> > st;

void rebuild(){
    for(register int i=1;i<=m;i++){
//      if(sd[to1[i]]==0||sd[u1[i]]==0) continue;
        int x=sd[u1[i]],y=sd[to1[i]];
        if(st.count(make_pair(x,y))||x==y) continue;
        st.insert((make_pair(x,y)));
        add2(x,y);add3(y,x);
    }
}

int dis[2][maxn];

void fir(){
    memset(dis[0],0xcf,sizeof(dis[0]));
    dis[0][sd[1]]=val[sd[1]];queue<int>q;q.push(sd[1]);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=Head2[x];i;i=Next2[i]){
            int y=to2[i];
            if(dis[0][y]>=dis[0][x]+val[y]) continue;
            dis[0][y]=dis[0][x]+val[y];
            q.push(y);
        }
    }
}

void sec(){
    memset(dis[1],0xcf,sizeof(dis[1]));
    dis[1][sd[1]]=val[sd[1]];queue<int>q;q.push(sd[1]);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=Head3[x];i;i=Next3[i]){
            int y=to3[i];
            if(dis[1][y]>=dis[1][x]+val[y]) continue;
            dis[1][y]=dis[1][x]+val[y];
            q.push(y);
        }
    }
}

int ans=0;

void calc(){
    for(register int i=1;i<=tot2;i++){
        int x=u2[i],y=to2[i];//错误笔记：写为to2[i]，开-Wall之后会有警告。
        ans=max(ans,dis[0][y]+dis[1][x]);
    }
    printf("%d\n",ans-val[sd[1]]);//错误笔记：将sd[1]写为1，所点后1所在的结点不一定是新1号点。
}

int main(){
    read(n);read(m);
    for(register int i=1;i<=m;i++){
        read(xx);read(yy);add1(xx,yy);
    }
    for(register int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    
//  puts("********************************");
//  printf("%d\n",cnt);
//  system("pause");
//  puts("********************************");
    
    rebuild();
    fir();sec();
    calc();
    return 0;
}