P3119 [USACO15JAN] Grass Cownoisseur G
显然我们可以先跑强连通分量，由\(x\)个点缩成的新点\(u\)权值为\(v[u]=x\)。
下文中的节点\(1\)均表示缩点后节点\(1\)所在的节点。
我们在缩点后的DAG上跑拓扑排序，预处理出\(fa[i]\)和\(fb[i]\)，分别表示“\(1\)到\(i\)路径的点权和”，“\(i\)到\(1\)路径的点权和”，后者可以建反图求解。
我们应该找到节点\(u,v\)使得：
- \(1\)可以到达\(u\)
- \(u\)到\(v\)有边
- \(v\)可以到达\(v\)
这样一个合法的路径（\(1\)到\(u\)，\(u\)逆行到\(v\)，\(v\)到\(i\)）就产生了，用\(fa[u]+fb[v]-v[1]\)更新答案即可。
注意，如果整个图是一个强连通分量，缩点后会只剩\(1\)个点，需要提前用\(v[1]\)更新答案，否则无法通过Subtask #1。
时间复杂度\(O(n+m)\)。
点击查看代码
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,m,dfn[N],low[N],tim,st[N],top,ans;
int v[N],ori[N],dega[N],degb[N],fa[N],fb[N];
bitset<N> in_stack;
vector<int> G[N],Ga[N],Gb[N];
queue<int> q;
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[++top]=u,in_stack[u]=1;
for(int i:G[u])
if(!dfn[i])
tarjan(i),
low[u]=min(low[u],low[i]);
else if(in_stack[i])
low[u]=min(low[u],dfn[i]);
if(dfn[u]==low[u]){
while(1){
int t=st[top--];
in_stack[t]=0,ori[t]=u,v[u]++;
if(t==u) break;
}
}
}
void topo(vector<int> G[],int deg[],int f[N],int s){
for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
memset(f,0,sizeof(int));
while(!q.empty()){
int u=q.front();
q.pop();
if(u==s||f[u]) f[u]+=v[u];
for(int i:G[u]){
f[i]=max(f[i],f[u]);
deg[i]--;
if(!deg[i]) q.push(i);
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G[u].emplace_back(v);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
ans=v[ori[1]];
for(int i=1;i<=n;i++){
for(int j:G[i]){
if(ori[i]!=ori[j]){
Ga[ori[i]].emplace_back(ori[j]);
Gb[ori[j]].emplace_back(ori[i]);
dega[ori[j]]++,degb[ori[i]]++;
}
}
}
topo(Ga,dega,fa,ori[1]);
topo(Gb,degb,fb,ori[1]);
for(int i=1;i<=n;i++){
if(!fb[i]) continue;
for(int j:Ga[i]){
if(!fa[j]) continue;
ans=max(ans,fb[i]+fa[j]-v[ori[1]]);
}
}
cout<<ans<<"\n";
return 0;
}