警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P1262」间谍网络 - 强连通分量

题意

传送门:洛谷 P1262 - 间谍网络

国家内部出现了一些间谍。有一部分间谍给钱就能控制。如果控制了一个间谍就可以控制其他的一些间谍。问最少需要多少钱可以控制所有的间谍。或者说这是不可能的。

可以说是非常模板的一道题了。

解法

显然如果一个强连通分量中有一个间谍被控制了,那么整个强连通分量(里的间谍)就都被控制了。

显然在图中没有环的时候,控制了所有入度为 \(\mathbf 0\) 的间谍就可以控制整张图。

缩点后维护两个信息:控制这个强连通分量所需的最少的钱数和强连通分量里编号最小的点。

根据上面的结论,显然可以推出,如果入度为 \(0\) 的点控制不了那么就 NO 了。

于是我们可以强连通分量缩点之后在 DAG 上按照上面的策略 DFS 就好了。

代码

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
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;

struct edge {
int from, to, next;
} e[20004];

int deg[3003], srcv[3003], val[3003], controlled;
int head[3003], cnt, ans, m;
bool vis[3003];

void addedge(int x, int y) {
e[++cnt] = (edge){x, y, head[x]}; head[x] = cnt;
}

int idx, scnt, dfn[3003], low[3003], scc[3003], id[3003];
stack<int> st;

void tarjan(int x) {
dfn[x] = low[x] = ++idx; vis[x] = true;
st.push(x);
for (int i = head[x]; i; i = e[i].next) {
int nx = e[i].to;
if (!dfn[nx]) {
tarjan(nx);
low[x] = min(low[x], low[nx]);
} else if (vis[nx]) {
low[x] = min(low[x], dfn[nx]);
}
}
if (dfn[x] == low[x]) {
val[++scnt] = srcv[x];
id[scnt] = x;
// printf("scc #%d:\n", scnt);
while (!st.empty()) {
int _ = st.top(); st.pop();
// printf("%d\n", _);
scc[_] = scnt;
vis[_] = false;
id[scnt] = min(id[scnt], _);
val[scnt] = min(val[scnt], srcv[_]);
if (_ == x) return;
}
}
}

void dfs(int x) {
if (vis[x]) return;
vis[x] = true;
controlled++;
for (int i = head[x]; i; i = e[i].next) {
dfs(e[i].to);
}
}

int n, k, x, y;

int main() {
memset(srcv, 0x3f, sizeof srcv);
scanf("%d%d", &n, &k);
while (k--) {
scanf("%d%d", &x, &y);
srcv[x] = min(srcv[x], y);
}
scanf("%d", &k);
while (k--) {
scanf("%d%d", &x, &y);
addedge(x, y);
}

for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}

n = scnt; m = cnt;
memset(head, 0, sizeof head); cnt = 0;
memset(vis, 0, sizeof vis);
for (int i = 1; i <= m; i++) {
if (scc[e[i].from] != scc[e[i].to]) {
deg[scc[e[i].to]]++;
addedge(scc[e[i].from], scc[e[i].to]);
}
}

for (int i = 1; i <= n; i++) {
if (!deg[i]) {
if (val[i] == 0x3f3f3f3f) {
printf("NO\n%d", id[i]);
return 0;
}
ans += val[i];
dfs(i);
}
}
assert(controlled == n);
printf("YES\n%d", ans);
return 0;
}

总结

很多 DAG 上的东西在一般的有向图上很难做,这是就可以考虑用 Tarjan 将图变成 DAG。