zqs`s blog

有朋自远方来，虽远必诛

Grass Cownoisseur G

发表于 更新于 分类于 Valine：

Tarjan缩点+SPFA最长路

传送门

看到这题有一个显然的贪心策略：可以经过一个牧场多次，那么在一个强连通分量里的牧场只要经过了其中的一个牧场剩下的一定都会被贝西吃掉。

所以先进行缩点。然后题目中说的可以逆向行走，我是这样处理的：

  • 先把图中的点分为两种：第一种是从点 $1$ 出发能够到达的，第二种是从该点出发能到点1的。
  • 不可能有一个点既是第一种又是第二种，毕竟缩点过后的图是一个DAG。
  • 我们记下从点 $1$ 出发到第一种点途中能经过最多的所有牧场总数，为 $QAQ[i]$，而从第二种点出发到点 $1$ 的点途中能经过的最 多的牧场总数记为 $QwQ[i]$。这里使用SPFA跑跑最长路即可。
  • 原谅我皮了一波。
  • 由于贝西要回到一号牧场，除了只吃第一个牧场所在的强连通分量所在的所有牧场之外，如果存在一个点 $u$ 是第二类点，$v$ 是第 一类点，且存在一条从 $u$ 到 $v$ 的有向边 $u\rigitrow v$，只要将这一条边反过来（逆向行走）就可以吃到 $QwQ[u]+QAQ[v]$ 个牧场的草。
  • 枚举点 $u$，然后在 $u$ 能到达的所有点种枚举点 $v$。

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <stack>
#include <queue>
#include <cstring>
#define MAXN 100005
#define MAXM 100005
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 131072, stdin), p1 == p2) ? EOF : *p1 ++)
char buf[131072], *p1 = buf, *p2 = buf;

inline int read() {//不会吧不会吧不会都0202年了还没有人用快读吧（滑稽.jpg
char ch;
int x(0);
while ((ch = gc) < 48);
while (ch >= 48) x = x * 10 + ch - 48, ch = gc;
return x;
}

inline int min(int x, int y) {return x < y ? x : y;}
inline int max(int x, int y) {return x > y ? x : y;}

struct Graph {
struct Edge {
int to, nxt;
} e[MAXM << 1];
int head[MAXN], tot;
inline void AddEdge(int u, int v) {
e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
}
} G1, G2, G3;

int low[MAXN], dfn[MAXN], cnt[MAXN], color[MAXN], QwQ[MAXN], QAQ[MAXN], vis[MAXN], scc, Num;
bool InStack[MAXN], mark[MAXN], mark2[MAXN];//mark表示每个点是否是第一类点，mark2标记是否为第二类点
std::stack<int> S;

inline void Tarjan(int u) {
dfn[u] = low[u] = ++ Num, S.push(u), InStack[u] = true;
for (int i(G1.head[u]); i; i = G1.e[i].nxt) {
int v(G1.e[i].to);
if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
else if (InStack[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++ scc;
int v;
do
v = S.top(), S.pop(), color[v] = scc, ++ cnt[scc], InStack[v] = false;
while (u != v);
}
}

std::queue<int> q;

inline void SPFA(Graph& G, bool * mark, int * TnT) {
memset(vis, 0, sizeof(vis));
q.push(color[1]);
TnT[color[1]] = cnt[color[1]];
mark[color[1]] = true;
while (q.size()) {
int u(q.front());
q.pop();
vis[u] = false;
for (int i(G.head[u]); i; i = G.e[i].nxt) {
int v(G.e[i].to);
if (!mark[v] || TnT[u] + cnt[v] > TnT[v]) {
TnT[v] = TnT[u] + cnt[v], mark[v] = true;
if (!vis[v]) q.push(v), vis[v] = true;
}
}
}
}

int main() {
int n(read()), m(read()), u, v;
while (m --)
    u = read(), v = read(), G1.AddEdge(u, v);
    for (int i(1); i <= n; ++ i) if (!dfn[i]) Tarjan(i);
    for (int u(1); u <= n; ++ u)
    for (int i(G1.head[u]); i; i = G1.e[i].nxt) {
        int v(G1.e[i].to);
        if (color[u] != color[v])
        G2.AddEdge(color[u], color[v]), G3.AddEdge(color[v], color[u]);
    }
    SPFA(G2, mark, QAQ), SPFA(G3, mark2, QwQ);
    int ans(cnt[color[1]]);
    for (int u(1); u <= scc; ++ u) if (mark2[u])
    for (int i(G2.head[u]); i; i = G2.e[i].nxt)
    if (mark[G2.e[i].to]) ans = max(ans, QwQ[u] + QAQ[G2.e[i].to] - cnt[color[1]]);
    printf("%d", ans);
}
-------------本文结束感谢您的阅读-------------