题解 P3119 【[USACO15JAN]草鉴定Grass Cownoisseur】

llllllQ · 2018-05-29 19:03:15 · 题解

tarjan+DFS+枚举

tarjan与最短路累问题的集合正向搜图和反向搜图并枚举每一条边求D[y]与B[x]的最大值

#include<cstdio>
#include<stack>
#include<memory.h>
#include<cmath>
#define MAXN 100005
#define MAXM 500005
using namespace std;
struct edge
{
    int x,y;
} E[MAXM];
int head[MAXN];
int next[MAXM];
int DFN[MAXN];
int COL[MAXN];
int LOW[MAXM];
int tm=0;
int id=0;
int tot;
int cnt[MAXN];
int b[MAXN],d[MAXN];
stack<int> S;
int V[MAXN];
int ans=-21474836;
int n,m;
void init()//重置数组
{
    memset(d,0,sizeof(d));
    memset(head,0,sizeof(head));
    memset(next,0,sizeof(next));
    id=0;
}
void ADD(int a,int b)//链式前向星
{
    id++;
    E[id].x=a;
    E[id].y=b;
    next[id]=head[a];
    head[a]=id;
}
void SCAN()
{
    int i;
    scanf("%d %d",&n,&m);
    init();
    for(i=1; i<=m; i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        ADD(a,b);
    }
}
void TJ(int x)//tarjan缩点涂色并记录色块点数
{
    DFN[x]=LOW[x]=++tm;
    S.push(x);
    V[x]=true;
    int i;
    for(i=head[x]; i; i=next[i])
    {
        int y=E[i].y;
        if(!DFN[y])
        {
            TJ(y);
            LOW[x]=min(LOW[x],LOW[y]);
        }
        else if(V[y])
        {
            LOW[x]=min(LOW[x],LOW[y]);
        }
    }
    if(LOW[x]==DFN[x])
    {
        tot++;
        int y=0;
        while(y!=x)
        {
            y=S.top();
            S.pop();
            V[y]=false;
            COL[y]=tot;
            cnt[tot]++;
        }
    }
}
void DFS(int x)//深搜更新d数组与b数组
{
    int i;
    for(i=head[x]; i; i=next[i])
    {
        int y=E[i].y;
        if(d[x]+cnt[y]>d[y])
            d[y]=d[x]+cnt[y];
        DFS(y);
    }
}//拓扑排序级SPFA效率略高
int main()
{
    SCAN();
    int i;
    for(i=1; i<=n; i++)
        if(!DFN[i])
            TJ(i);
    init();
    for(i=1; i<=m; i++)
    {
        int x=E[i].x,y=E[i].y;
        if(COL[x]!=COL[y])ADD(COL[x],COL[y]);
    }
    n=tot;
    m=id;
    int s=COL[1];
    d[s]=cnt[s];
    DFS(s);
    memcpy(b,d,sizeof(b));
    init();
    for(i=1; i<=m; i++)
        ADD(E[i].y,E[i].x);
    d[s]=cnt[s];
    DFS(s);
    for(i=1; i<=m; i++)
    {
        if(d[E[i].y]&&b[E[i].x])
            ans=max(ans,d[E[i].y]+b[E[i].x]-cnt[s]);
    }
    printf("%d",ans);
    return 0;
}