P3119 [USACO15JAN]草鉴定Grass Cownoisseur

· · 题解

https://www.luogu.org/problemnew/show/P3119

粗暴的Tarjan强连通分量+最短路Dijkstra

本题代码==缩点模板套上堆优化Dj 粗暴得不用考虑其他乱七八糟的情况

至于逆向走的问题，在最短路中加上判断情况就行

优先队列的顺序一定要写对！效率天差地别

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<cctype>
using namespace std;
const int min(int a,int b) {return a<b ? a:b;}
const int maxn=100003;
struct data{
    int d,u,br; //d:权值 u:点编号 br:是否已进行了逆向边操作
    bool operator < (const data &tmp) const{
        return d>tmp.d;
    } //又一次符号写反导致超时
};
priority_queue <data> h;
vector <int> g1[maxn],g2[maxn],g3[maxn]; //g1:存原图；g2:存新图 g3:存新图的反向边
int dfn[maxn],low[maxn],st[maxn],be[maxn],d[2][maxn],tot[maxn];
int dfs_clock,cnt,top,n,m;
inline int getint() //快读
{
    char c=getchar(); int x=0;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
void tarjan(int x) //裸的缩点模板
{
    dfn[x]=low[x]=++dfs_clock;
    st[++top]=x;
    int len=g1[x].size();
    for(int i=0;i<len;i++)
    {
        int to=g1[x][i];
        if(!dfn[to])
        {
            tarjan(to);
            low[x]=min(low[x],low[to]);
        }else if(!be[to]) low[x]=min(low[x],dfn[to]);
    }
    if(dfn[x]==low[x])
    {
        be[x]=++cnt; tot[cnt]++;
        while(st[top]!=x)
        {
            be[st[top--]]=cnt; tot[cnt]++;
        }
        top--;
    }
}
int main()
{
    freopen("P3119.in","r",stdin);
    n=getint(); m=getint();
    int q1,q2;
    for(int i=1;i<=m;i++)
    {
        q1=getint(); q2=getint();
        g1[q1].push_back(q2);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++) //建新图
    {
        int len=g1[i].size();
        for(int j=0;j<len;j++)
        {
            int to=g1[i][j];
            if(be[i]!=be[to])
            {
                g2[be[i]].push_back(be[to]);
                g3[be[to]].push_back(be[i]);
            }
        }
    }
//------以上是裸的tarjan------------
//最短路部分（加了堆优化）
    h.push((data){0,be[1],0});  //注意是跑缩点后的图，所以从点1所属的强连通分量开始跑
    while(!h.empty())
    {
        data x=h.top(); h.pop();
        if(x.d!=d[x.br][x.u]) continue;
        int u=x.u,len=g2[u].size();
        for(int i=0;i<len;i++)
        {
            int to=g2[u][i];
            if(d[x.br][to]<d[x.br][u]+tot[to])
            {
                d[x.br][to]=d[x.br][u]+tot[to];
                h.push((data){d[x.br][to],to,x.br});
            }
        }
        if(x.br==0) //逆向边操作（去掉这块就是裸的Dj算法了）
        {
            len=g3[u].size();
            for(int i=0;i<len;i++)
            {
                int to=g3[u][i];
                if(d[1][to]<d[0][u]+tot[to])
                {
                    d[1][to]=d[0][u]+tot[to];
                    h.push((data){d[1][to],to,1});
                }
            }
        }
    }
    printf("%d",max(d[0][be[1]],d[1][be[1]])); //终点的最大值
    return 0;
}