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

· · 题解

此题难在建模。

看到这道题，首先想到的是Tarjan缩点，将图上的强连通分量（强连通分量中的任意两点相互可达）缩成点，形成一个新图，可以保证新图上无环（因为如果有环则环一定在一个强连通分量中），然后再考虑接下来的步骤。

简单概述一下Tarjan求强连通分量的过程。我们用DFS解决这个问题。在DFS的过程中，对节点有一个访问序号，记为dfn_i。然后，对于节点i，我们定义其在DFS树上，中间节点在节点i的子树中且不经过节点i到其DFS树上的父亲节点fa的边(i,fa)（如果有重边则可以经过）所能到达的最小的时间戳，即low_i=min~dfn_a。对于一个节点i，如果low_i=dfn_i，那么肯定有一个包含节点i的新强联通分量。如何计算这个强连通分量内的节点呢？我们用一个数据结构栈（STL~stack）解决这个问题。我们每访问一个新的节点，将该节点加入栈；对一个节点的DFS过程结束时，如果找到一个新的强连通分量时，依次将栈中的元素弹出，直到弹出的元素是当前节点为止。

由于这个DFS过程需要访问一个节点所有的出边，我们可以用邻接链表存边（vector或链式前向星）。时间复杂度O(N+M)。

然后便是在DAG上进行操作的问题了。看了下其他大佬的题解，都是分类，枚举。这里介绍一个分层图的方法。

考虑一张图，将这个图复制一份，点的编号从1~N到(N+1)~(N+N)。然后在两层图中连边。对于原图上的每一条边，从原图的指向点到新图的起始点连一条边，边权与原边相同，代表逆向走一条边。逆向走了一条边，就不能再逆向走了，所以从上面的一层（新图）无法回到下面的一层。最后跑一遍SPFA，节点1所在的强连通分量编号，到节点1所在的强连通分量编号+N上的最长路，就是最后的答案。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int maxn=100010;
const int inf=2e9;
vector<int>G[maxn];
vector<int>G1[maxn*2];
int n,m,u,v,op,index_,dfn[maxn],low[maxn],bcc[maxn],siz[maxn*2],cnt,dist[maxn*2];
bool tf[maxn*2];
stack<int>st;
queue<int>q;
void dfs(int cur)
{
    dfn[cur]=low[cur]=++index_;
    tf[cur]=true;
    st.push(cur);
    for(int i=0;i<G[cur].size();i++)
    {
        if(!dfn[G[cur][i]])
        {
            dfs(G[cur][i]);
            low[cur]=min(low[cur],low[G[cur][i]]);
        }
        else if(tf[G[cur][i]])low[cur]=min(low[cur],dfn[G[cur][i]]);
    }
    if(dfn[cur]==low[cur])
    {
        cnt++;
        while(st.top()!=cur)
        {
            bcc[st.top()]=cnt;
            tf[st.top()]=false;
            siz[cnt]++;
            st.pop();
        }
        bcc[st.top()]=cnt;
        tf[st.top()]=false;
        siz[cnt]++;
        st.pop();
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
    for(int i=1;i<=cnt;i++)siz[cnt+i]=siz[i];
    for(int i=1;i<=n;i++)for(int j=0;j<G[i].size();j++)if(bcc[i]!=bcc[G[i][j]])
    {
        G1[bcc[i]].push_back(bcc[G[i][j]]);
        G1[bcc[G[i][j]]].push_back(bcc[i]+cnt);
        G1[bcc[i]+cnt].push_back(bcc[G[i][j]]+cnt);
    }
    tf[bcc[1]]=true;q.push(bcc[1]);
    while(!q.empty())
    {
        int x=q.front();
        for(int i=0;i<G1[x].size();i++)if(dist[G1[x][i]]<dist[x]+siz[x])
        {
            dist[G1[x][i]]=dist[x]+siz[x];
            if(!tf[G1[x][i]])tf[G1[x][i]]=true,q.push(G1[x][i]);
        }
        q.pop();tf[x]=false;
    }
    printf("%d\n",dist[bcc[1]+cnt]);
    return 0;
}

用这样的思想，还可以解决一道这样的问题：给定一个有向图G，有m张优惠券，可以把一条边的边权改成一个固定值k，求节点s到节点t之间最短路的长度和方案数。方法是建立一个m+1层的多层图，层与层之间的边的权值都为k，然后跑最短路。由于用了优惠券不一定能达到优化的目的，所以答案为min(t,t+n,t+n+n,...)。方案数也可如此做。

感谢实哥大佬提供的hack数据，本篇题解其实有一个瑕疵，但由于数据水没有测出来。

如果整个图是一个强连通分量，转换成新图的时候就不会加边，所以最后节点的最长路是错误的。

解决方法也显而易见，就是建新图的时候从起点直接往终点连一条边权为起点代表的强连通分量的大小的边。

不贴代码了（其实只用改一行）