瞎记一下做法。
Eleveslaine
·
·
个人记录
P3119
简要题意：给定 n 点 m 边的有向图，从 1 号点出发，可以任意多次地经过同一条点和边，并且可以进行至多一次逆行，最终回到 1 号点。求最多经过不同点的个数。
数据范围：1 \le n,m \le 10^5。
- Tarjan 缩点，建立分层图 G'=(V',E')。具体地，设 \mathrm{scc}[u] 表示点 u 所在的强连通分量编号，共有 N 个强连通分量，第 i(1 \le i \le N) 个强连通分量包含的点数为 w[i]，(u,v,w) 表示一条 u\to v，权为 w 的有向边（这里是点权化边权）。则
\begin{aligned}
V'&=\left\{\mathrm{scc}[u],\mathrm{scc}[u]+N\mid u\in V\right\} \\
E'&=\left\{(\mathrm{scc}[u],\mathrm{scc}[v],w[\mathrm{scc}[u]]),(\mathrm{scc}[u]+N,\mathrm{scc}[v]+N,w[\mathrm{scc}[u]]),(\mathrm{scc}[v],\mathrm{scc}[u]+N,w[\mathrm{scc}[v]])\mid (u,v)\in E\right\}
\end{aligned}
-
cnblogs SlaineTroyard 是我本人。