（tarjan 缩点）洛谷 P3119 USACO15JAN Grass Cownoisseur G 题解

题意

Farmer John 在他的农场中安装了 $m$ 条单向牛道。农场由 $n$ 块草场组成，编号为 $1$ 到 $n$，每条单向牛道连接一对草场。

众所周知，Bessie 喜欢尽可能多地品尝不同草场的牧草。她每天从草场 $1$ 出发，访问一系列草场后返回草场 $1$。她试图最大化沿途经过的不同草场数量（重复访问的草场只算一次）。

由于单向路径的限制，Bessie 担心这会减少她每日路线中可以访问的草场数量。她想知道如果她违反规则，在路线中最多逆向通过某条道路一次，最多能品尝多少草场的牧草。请计算她从草场 $1$ 出发并返回的情况下，最多能访问的不同草场数量。注意 Bessie 在整个旅程中最多只能逆向通过一条道路，且同一条路径不能逆向两次。

$1\le n,m\le 10^5$。

思路

如果不能违反规则，重复走的不算，可以 tarjan 缩点。因为最终还要回到 $1$，缩点后对于有向边 $u\to v$，我们以 $sccsi{z}_v$ 作为边权跑最长路；由于缩点后的图比较离散，用 spfa 跑可重点最长路也是可以的（正解当然是稳定 $\Theta (n)$ 的拓扑排序）。

现在多了一条可以违反规则的条件，可以从 $v$ 走回 $u$，我们总不能枚举每条边加反边删边吧。我们怎么做到把所有加的反边一起计算呢？于是可以建分层图。

对于 E { u → v } \mathbb{E}\{u\to v\} E{u→v}，我们建一个 E ′ { u + n → v + n } \mathbb{E}'\{u+n\to v+n\} E′{u+n→v+n}，此时上下图等价；我们用“反边” $v\to u+n$ 连接分层图，从 $1$ 开始绕一圈回到 $1$，等价于 $1$ 到 $1$ 和 $1$ 到 $1+n$ 取最优解。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=6e5+9;
ll n,m;
vector<ll>G[N];
ll idx,head[N];
struct edge
{ll to,next,w;
}e[N];
void addedge(ll u,ll v,ll w)
{idx++;e[idx].to=v;e[idx].next=head[u];e[idx].w=w;head[u]=idx;
}
ll ti,dfn[N],low[N],stk[N],top;
ll scccnt,sccno[N],num[N];
void tarjan(ll u)
{dfn[u]=low[u]=++ti;stk[top++]=u;for(auto v:G[u]){if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(!sccno[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){scccnt++;while(1){ll tem=stk[--top];sccno[tem]=scccnt;num[scccnt]++;if(u==tem)break;}}
}
ll dis[N];
bool vis[N];
void spfa(ll s)
{queue<ll>q;q.push(s);while(!q.empty()){ll u=q.front();q.pop();vis[u]=0;for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(dis[u]+w>dis[v]){dis[v]=dis[u]+w;if(!vis[v]){vis[v]=1;q.push(v);}}}}
}
int main()
{scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){ll u,v;scanf("%lld%lld",&u,&v);G[u].push_back(v);G[v].push_back(u+n);G[u+n].push_back(v+n); }for(int i=1;i<=2*n;i++)if(!dfn[i])tarjan(i);for(int u=1;u<=2*n;u++){for(auto v:G[u]){ll su=sccno[u],sv=sccno[v];if(su==sv)continue;addedge(su,sv,num[sv]);}}spfa(sccno[1]);printf("%lld",max(num[sccno[1]],max(dis[sccno[1]],dis[sccno[1+n]])));return 0;
}