摄像头

题意

每个摄像头站在一个位置上，并会监视若干个固定地点。

如果某个摄像头所在的位置没有被其它摄像头监视，那么它就能被砸掉；砸掉以后，它也就不再监视别人。

问最后还能剩下多少个摄像头。

思路

关系图

这张图展示“监视关系”如何转成有向图：

digraph G {
  rankdir=LR;
  5 -> 4;
  5 -> 6;
  6 -> 5;
}

边 u -> v 表示 u 在监视 v 所在的位置。因此点 v 只有在没有其它点指向它时，才可以被砸掉。像图中的 5 和 6 互相监视，就会形成一个删不掉的环。

先看一个小数据暴力：

cpp

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const int MAXP = 505;

int n;
int pos[MAXN];
vector<int> watch_pos[MAXN];
vector<int> cameras_at_pos[MAXP];
int in_mask[MAXN];        // in_mask[i] : 哪些摄像头会监视第 i 个摄像头
int memo[1 << MAXN];

int solve_mask(int mask) {
    if (memo[mask] != -1) {
        return memo[mask];
    }

    int best = __builtin_popcount((unsigned) mask);
    bool can_remove = false;

    for (int i = 0; i < n; i++) {
        if (((mask >> i) & 1) == 0) {
            continue;
        }

        // 还存活的摄像头里，没有别人监视它，它就可以被砸掉。
        if ((in_mask[i] & mask) == 0) {
            can_remove = true;
            best = min(best, solve_mask(mask ^ (1 << i)));
        }
    }

    if (!can_remove) {
        memo[mask] = __builtin_popcount((unsigned) mask);
    } else {
        memo[mask] = best;
    }
    return memo[mask];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < MAXP; i++) {
        cameras_at_pos[i].clear();
    }

    for (int i = 0; i < n; i++) {
        watch_pos[i].clear();

        int m;
        cin >> pos[i] >> m;
        for (int j = 0; j < m; j++) {
            int y;
            cin >> y;
            watch_pos[i].push_back(y);
        }
        cameras_at_pos[pos[i]].push_back(i);
    }

    memset(in_mask, 0, sizeof(in_mask));
    for (int i = 0; i < n; i++) {
        bool linked[MAXN] = {};

        for (int y : watch_pos[i]) {
            for (int v : cameras_at_pos[y]) {
                if (v == i || linked[v]) {
                    continue;
                }
                linked[v] = true;
                in_mask[v] |= 1 << i;
            }
        }
    }

    int full = (1 << n) - 1;
    memset(memo, -1, sizeof(memo));
    memo[0] = 0;

    cout << solve_mask(full) << '\n';
    return 0;
}

暴力是在“当前还剩哪些摄像头”这个状态上不断搜索，枚举哪些摄像头现在可以砸掉。它能帮助理解过程，但正式解法没必要真的去搜顺序。

关键建模是：

如果摄像头 u 监视到了摄像头 v 所在的位置，就连边 u -> v。
那么摄像头 v 当前能被砸掉，当且仅当没有其它点指向它，也就是当前入度为 0。

于是题目就完全变成了：

反复删除入度为 0 的点
每删掉一个点，就把它发出的边一并删除

这就是标准的 Kahn 拓扑排序过程。

实现时先用 cameras_at_pos[x] 记录每个位置上有哪些摄像头。然后枚举摄像头 u 监视的每个地点 y，把位置正好为 y 的所有摄像头都连成 u -> v。

代码里把这部分单独写成了一个 TopologicalSort 结构，接口和你算法书里的拓扑模板保持一致：add_edge() 负责加边，kahn_prune() 负责反复删除入度为 0 的点。

最后做一次队列版拓扑删除，被删掉的点数记作 removed，答案就是 n - removed。

代码

cpp

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXP = 505;

int n;
int pos[MAXN];                    // pos[i] : 第 i 个摄像头所在的位置
vector<int> watch_pos[MAXN];      // watch_pos[i] : 第 i 个摄像头监视的地点
vector<int> cameras_at_pos[MAXP]; // cameras_at_pos[x] : 位置 x 上有哪些摄像头

struct TopologicalSort {
    int n;
    vector<vector<int>> graph;
    vector<int> indeg;

    explicit TopologicalSort(int n = 0) {
        init(n);
    }

    void init(int _n) {
        n = _n;
        graph.assign(n + 1, vector<int>());
        indeg.assign(n + 1, 0);
    }

    void add_edge(int u, int v) {
        graph[u].push_back(v);
        indeg[v]++;
    }

    // 不断删除入度为 0 的点，返回被删除的点数。
    int kahn_prune() {
        queue<int> q;
        vector<int> deg = indeg;
        int removed = 0;

        for (int i = 1; i <= n; i++) {
            if (deg[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            removed++;

            for (int v : graph[u]) {
                deg[v]--;
                if (deg[v] == 0) {
                    q.push(v);
                }
            }
        }

        return removed;
    }
};

TopologicalSort topo;

void read_input() {
    cin >> n;
    topo.init(n);

    for (int i = 0; i < MAXP; i++) {
        cameras_at_pos[i].clear();
    }

    for (int i = 1; i <= n; i++) {
        watch_pos[i].clear();

        int m;
        cin >> pos[i] >> m;

        for (int j = 1; j <= m; j++) {
            int y;
            cin >> y;
            watch_pos[i].push_back(y);
        }

        cameras_at_pos[pos[i]].push_back(i);
    }
}

void build_graph() {
    for (int u = 1; u <= n; u++) {
        bool linked[MAXN] = {};

        for (int y : watch_pos[u]) {
            for (int v : cameras_at_pos[y]) {
                // 题目要求是“其他摄像头”，自己监视自己不算。
                if (v == u || linked[v]) {
                    continue;
                }
                linked[v] = true;
                topo.add_edge(u, v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    build_graph();

    int removed = topo.kahn_prune();
    cout << n - removed << '\n';

    return 0;
}

复杂度

设建图后总边数为 E，时间复杂度 $O(n + E)$ ，空间复杂度 $O(n + E)$ 。

总结

这题表面上是一个“不断砸摄像头”的过程题，实质上就是有向图删点。把“可砸”翻译成“入度为 0”，题目就直接落成拓扑排序模板了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

关系图

代码

复杂度

总结

一图流解析